)
这道题的核心思路是：只交换 nums1[i] == nums2[i] 的位置，如果某个数字出现次数过多，再从其他位置引入交换。
下面给出一个清晰、高效的 Java 实现，包含详细注释：
class Solution {
public long minimumTotalCost(int[] nums1, int[] nums2) {
int n = nums1.length;
long ans = 0L;
// 1. 统计所有数字在nums1和nums2中出现的总次数
// 如果某个数字出现次数 > n，则无解
int[] totalFreq = new int[n + 1];
for (int i = 0; i < n; i++) {
totalFreq[nums1[i]]++;
totalFreq[nums2[i]]++;
}
for (int i = 1; i <= n; i++) {
if (totalFreq[i] > n) {
return -1;
}
}
// 2. 统计需要交换的位置（nums1[i] == nums2[i]）
int[] swapFreq = new int[n + 1]; // 记录需要交换的数字出现次数
int swapCount = 0; // 需要交换的总次数
int maxFreq = 0; // 出现最多的数字的次数
int maxNum = 0; // 出现最多的数字
for (int i = 0; i < n; i++) {
if (nums1[i] == nums2[i]) {
int val = nums1[i];
swapFreq[val]++;
swapCount++;
ans += i; // 这些位置必须参与交换，代价累加
if (swapFreq[val] > maxFreq) {
maxFreq = swapFreq[val];
maxNum = val;
}
}
}
// 3. 如果众数不超过一半，内部交换即可
if (maxFreq * 2 <= swapCount) {
return ans;
}
// 4. 需要从外部引入交换
int need = maxFreq * 2 - swapCount; // 还需要引入的次数
for (int i = 0; i < n && need > 0; i++) {
// 跳过已经需要交换的位置
if (nums1[i] == nums2[i]) {
continue;
}
// 跳过包含众数的位置（引入它们无法解决问题）
if (nums1[i] == maxNum || nums2[i] == maxNum) {
continue;
}
// 引入这个位置参与交换
ans += i;
need--;
}
// 5. 如果引入后仍然不够，说明无解
if (need > 0) {
return -1;
}
return ans;
}
}
算法要点说明
步骤 说明
无解判断 如果某个数字在 nums1 和 nums2 中出现的总次数 > n，则无论如何都无法让所有位置不相等
必须交换的位置 nums1[i] == nums2[i] 的位置必须参与交换，代价至少为这些下标之和
内部交换 如果众数出现次数 ≤ 需要交换总数的一半，可以在这些位置内部两两交换完成
外部引入 如果众数过多，需要从 nums1[i] != nums2[i] 且不包含众数的位置引入交换
贪心选择 从下标最小的位置开始引入，保证总代价最小
复杂度分析
- 时间复杂度：O(n)，只需遍历数组常数次
- 空间复杂度：O(n)，用于统计频率
示例验证
示例1：nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]
- 所有位置都需要交换，众数1出现1次，swapCount=5，1*2 ≤ 5，直接返回下标和 0+1+2+3+4=10 ✓
示例2：nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3]
- 需要交换的位置：下标1(2=2)、下标2(2=2)，swapCount=2，众数2出现2次，2*2 > 2，需要引入
- 从下标0(2≠1，不含众数2？不，nums1[0]=2)跳过，下标3(1≠3，不含2)引入，下标4(3≠3？不相等)引入
- 最终代价：1+2+3+4=10 ✓
示例3：nums1 = [1,2,2], nums2 = [1,2,2]
- 数字2出现4次 > n=3，直接返回-1 ✓
这个实现简洁高效，直接利用了贪心思想，是这道题的标准解法。
