千问 LeetCode 2499.让数组不相等的最小总代价 public long minimumTotalCost(int[] nums1, int[] nums2)

这道题的核心思路是只交换 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)用于统计频率示例验证示例1nums1 [1,2,3,4,5], nums2 [1,2,3,4,5]- 所有位置都需要交换众数1出现1次swapCount51*2 ≤ 5直接返回下标和 0123410 ✓示例2nums1 [2,2,2,1,3], nums2 [1,2,2,3,3]- 需要交换的位置下标1(22)、下标2(22)swapCount2众数2出现2次2*2 2需要引入- 从下标0(2≠1不含众数2不nums1[0]2)跳过下标3(1≠3不含2)引入下标4(3≠3不相等)引入- 最终代价123410 ✓示例3nums1 [1,2,2], nums2 [1,2,2]- 数字2出现4次 n3直接返回-1 ✓这个实现简洁高效直接利用了贪心思想是这道题的标准解法。