题目描述
给你两个下标从 0 开始的整数数组 nums1
和 nums2
,两者长度都为 n
。
每次操作中,你可以选择交换 nums1
中任意两个下标处的值。操作的 开销 为两个下标的 和。
你的目标是对于所有的 0 <= i <= n - 1
,都满足 nums1[i] != nums2[i]
,你可以进行 任意次 操作,请你返回达到这个目标的 最小 总代价。
请你返回让 nums1
和 nums2
满足上述条件的 最小总代价,如果无法达成目标,返回 -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 的方案。
输入: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,是所有方案中的最小代价。
输入:nums1 = [1,2,2], nums2 = [1,2,2]
输出:-1
解释:
不管怎么操作,都无法满足题目要求。
所以返回 -1。
限制
n == nums1.length == nums2.length
1 <= n <= 10^5
1 <= nums1[i], nums2[i] <= n
算法
(思维题) $O(n)$
- 统计两个数组中出现相同数字的位置,这些位置一定是需要被替换的。
- 如果这些相同元素的位置中,不存在某个元素的出现次数超过总位置数的一半,则可以直接返回这些位置下标总和,即内部交换解决,证明如下:
- 如果总位置数为偶数,则总可以通过内部两两交换完成。
- 如果总位置数为奇数,则再分为两种情况:
- 如果位置 $0$ 上的元素相同,则内部就可以利用位置 $0$ 额外交换一次,不会增加答案。
- 如果位置 $0$ 上的元素不同,则必定可以将位置 $0$ 上的值换入到某个相同元素的位置上,使得最终相同元素的位置个数变为偶数,且不会打破 不存在某个元素的出现次数超过总位置数的一半 的前提。再根据个数为偶数情况已经成立,则此时奇数的情况也成立。
- 如果存在某个元素的出现次数超过了一半,则需要从 外部位置 换入。换入的条件是
nums1
的元素以及nums2
对应位置的元素,都不和该出现频率最高的元素相同(否则换入换出没有意义)。期望换入的个数为 两倍的最大频数 减去 总数量。通过遍历数组逐一寻找,如果最终找不到足够多的外部元素换入,则返回 $-1$。
时间复杂度
- 最多遍历数组三次,时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
#define LL long long
class Solution {
public:
LL minimumTotalCost(vector<int>& nums1, vector<int>& nums2) {
const int n = nums1.size();
LL ans = 0;
int tot = 0;
unordered_map<int, int> h;
for (int i = 0; i < n; i++) {
if (nums1[i] != nums2[i])
continue;
h[nums1[i]]++;
tot++;
ans += i;
nums1[i] = -1;
}
int x = -1, c;
for (const auto &[k, v] : h)
if (v * 2 > tot) {
x = k;
c = v;
break;
}
if (x == -1)
return ans;
c -= tot - c;
for (int i = 0; i < n && c > 0; i++)
if (nums1[i] != -1 && nums1[i] != x && nums2[i] != x) {
ans += i;
c--;
}
if (c > 0)
return -1;
return ans;
}
};
看来思维还是不够啊!!想到了一半,中间卡住没想下去!/(ㄒoㄒ)/