class Solution {
public:
long long minimumTotalCost(vector<int>& nums1, vector<int>& nums2) {
}
};
2499. 让数组不相等的最小总代价
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。
每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的 开销 为两个下标的 和 。
你的目标是对于所有的 0 <= i <= n - 1 ，都满足 nums1[i] != nums2[i] ，你可以进行 任意次 操作，请你返回达到这个目标的 最小 总代价。
请你返回让 nums1 和 nums2 满足上述条件的 最小总代价 ，如果无法达成目标，返回 -1 。
示例 1：
输入：nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5] 输出：10 解释： 实现目标的其中一种方法为： - 交换下标为 0 和 3 的两个值，代价为 0 + 3 = 3 。现在 nums1 = [4,2,3,1,5] 。 - 交换下标为 1 和 2 的两个值，代价为 1 + 2 = 3 。现在 nums1 = [4,3,2,1,5] 。 - 交换下标为 0 和 4 的两个值，代价为 0 + 4 = 4 。现在 nums1 = [5,3,2,1,4] 。 最后，对于每个下标 i ，都有 nums1[i] != nums2[i] 。总代价为 10 。 还有别的交换值的方法，但是无法得到代价和小于 10 的方案。
示例 2：
输入：nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3] 输出：10 解释： 实现目标的一种方法为： - 交换下标为 2 和 3 的两个值，代价为 2 + 3 = 5 。现在 nums1 = [2,2,1,2,3] 。 - 交换下标为 1 和 4 的两个值，代价为 1 + 4 = 5 。现在 nums1 = [2,3,1,2,2] 。 总代价为 10 ，是所有方案中的最小代价。
示例 3：
输入：nums1 = [1,2,2], nums2 = [1,2,2] 输出：-1 解释： 不管怎么操作，都无法满足题目要求。 所以返回 -1 。
提示：
n == nums1.length == nums2.length1 <= n <= 1051 <= nums1[i], nums2[i] <= n原站题解
cpp 解法, 执行用时: 136 ms, 内存消耗: 104.1 MB, 提交时间: 2022-12-20 09:58:57
class Solution {
public:
long long minimumTotalCost(vector<int>& a, vector<int>& b) {
int n = a.size(), repeat = 0; // 相等位置a[i]==b[i]的数量
long long s = 0; // 相等位置的下标和
int val = -1, x = 0; // 摩尔投票的结果和剩余票数
for (int i = 0; i < n; ++i) {
if (a[i] == b[i]) {
if (x == 0) val = a[i];
x += 2 * (val == a[i]) - 1; // 经典摩尔投票
repeat++;
s += i;
}
}
int cnt = 0; // 过半的唯一可能就是val，cnt表示val出现的次数
for (int i = 0; i < n; ++i) {
cnt += a[i] == b[i] && a[i] == val;
}
if (cnt * 2 < repeat) return s; // 没有过半，s可以直接作为结果
int m = 2 * cnt - repeat; // 表示需要和“良民”交换的数量
for (int i = 0; i < n && m > 0; ++i) {
// 用来交换的点，ab均不能有val，也不能是相等位置
if (a[i] != val && b[i] != val && a[i] != b[i]) {
s += i;
m--;
}
}
if (m > 0) return -1; // 没能引入足够的“良民”，失败，返回-1
return s;
}
};
python3 解法, 执行用时: 160 ms, 内存消耗: 26.1 MB, 提交时间: 2022-12-20 09:56:45
class Solution:
def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:
ans = swap_cnt = mode_cnt = mode = 0
cnt = [0] * (len(nums1) + 1)
for i, (x, y) in enumerate(zip(nums1, nums2)):
if x == y:
ans += i
swap_cnt += 1
cnt[x] += 1
if cnt[x] > mode_cnt:
mode_cnt, mode = cnt[x], x
for i, (x, y) in enumerate(zip(nums1, nums2)):
if mode_cnt * 2 <= swap_cnt: break
if x != y and x != mode and y != mode:
ans += i
swap_cnt += 1
return ans if mode_cnt * 2 <= swap_cnt else -1
golang 解法, 执行用时: 116 ms, 内存消耗: 9.5 MB, 提交时间: 2022-12-20 09:56:25
func minimumTotalCost(nums1, nums2 []int) (ans int64) {
var swapCnt, modeCnt, mode int
cnt := make([]int, len(nums1)+1)
for i, x := range nums1 {
if x == nums2[i] {
ans += int64(i)
swapCnt++
cnt[x]++
if cnt[x] > modeCnt {
modeCnt, mode = cnt[x], x
}
}
}
for i, x := range nums1 {
if modeCnt*2 <= swapCnt {
break
}
if x != nums2[i] && x != mode && nums2[i] != mode {
ans += int64(i)
swapCnt++
}
}
if modeCnt*2 > swapCnt {
return -1
}
return
}
java 解法, 执行用时: 3 ms, 内存消耗: 58.9 MB, 提交时间: 2022-12-20 09:56:11
class Solution {
public long minimumTotalCost(int[] nums1, int[] nums2) {
long ans = 0L;
int swapCnt = 0, modeCnt = 0, mode = 0, n = nums1.length;
int[] cnt = new int[n + 1];
for (int i = 0; i < n; ++i) {
int x = nums1[i];
if (x == nums2[i]) {
ans += i;
++swapCnt;
++cnt[x];
if (cnt[x] > modeCnt) {
modeCnt = cnt[x];
mode = x;
}
}
}
for (int i = 0; i < n && modeCnt * 2 > swapCnt; ++i) {
int x = nums1[i], y = nums2[i];
if (x != y && x != mode && y != mode) {
ans += i;
++swapCnt;
}
}
return modeCnt * 2 > swapCnt ? -1 : ans;
}
}
cpp 解法, 执行用时: 128 ms, 内存消耗: 104.6 MB, 提交时间: 2022-12-20 09:55:55
class Solution {
public:
long long minimumTotalCost(vector<int> &nums1, vector<int> &nums2) {
long ans = 0L;
int swap_cnt = 0, mode_cnt = 0, mode, n = nums1.size(), cnt[n + 1];
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; ++i)
if (int x = nums1[i]; x == nums2[i]) {
ans += i;
++swap_cnt;
++cnt[x];
if (cnt[x] > mode_cnt) {
mode_cnt = cnt[x];
mode = x;
}
}
for (int i = 0; i < n && mode_cnt * 2 > swap_cnt; ++i) {
int x = nums1[i], y = nums2[i];
if (x != y && x != mode && y != mode) {
ans += i;
++swap_cnt;
}
}
return mode_cnt * 2 > swap_cnt ? -1 : ans;
}
};