Medium

题目描述

给你两个大小为 n 的整数数组 nums1 和 nums2。

你可以对这两个数组执行以下两种操作任意次数：

  • 数组内交换：选择两个下标 i 和 j。然后，选择交换 nums1[i] 和 nums1[j]，或者交换 nums2[i] 和 nums2[j]。此操作不产生费用。
  • 数组间交换：选择一个下标 i。然后，交换 nums1[i] 和 nums2[i]。此操作产生 1 的费用。

返回使 nums1 和 nums2 相同的最小代价。如果无法使它们相同，返回 -1。

示例 1：

输入：nums1 = [10,20], nums2 = [20,10]
输出：0
解释：
交换 nums2[0] = 20 和 nums2[1] = 10。
nums2 变为 [10, 20]。
此操作不产生费用。
nums1 和 nums2 现在相同。代价为 0。

示例 2：

输入：nums1 = [10,10], nums2 = [20,20]
输出：1
解释：
交换 nums1[0] = 10 和 nums2[0] = 20。
nums1 变为 [20, 10]。
nums2 变为 [10, 20]。
此操作代价为 1。
交换 nums2[0] = 10 和 nums2[1] = 20。
nums2 变为 [20, 10]。
此操作不产生费用。
nums1 和 nums2 现在相同。代价为 1。

示例 3：

输入：nums1 = [10,20], nums2 = [30,40]
输出：-1
解释：
无法使两个数组相同。因此，答案为 -1。

约束条件：

  • 2 <= n == nums1.length == nums2.length <= 8 * 10^4
  • 1 <= nums1[i], nums2[i] <= 8 * 10^4

解题思路

这道题的关键在于理解数组内交换是免费的，因此位置不重要，只有频率重要。

解题思路

  1. 频率统计：由于数组内交换免费，我们只需要关注每个值在两个数组中的出现频率。

  2. 可行性判断：对于任意值 v，如果 cnt1[v] + cnt2[v] 是奇数，说明总数为奇数，无法通过交换使两个数组在该值上达到相同频率，返回 -1。

  3. 最小交换次数计算：

    • 对于值 v，设 diff[v] = |cnt1[v] - cnt2[v]|
    • 这表示需要在两个数组间转移的该值的数量
    • 每次数组间交换可以同时修正两个不匹配（一个数组减少某值，另一个数组增加该值）
    • 因此最小交换次数为 sum(diff[v]) / 4

  4. 算法流程：

    • 统计两个数组中每个值的频率
    • 检查每个值的总频率是否为偶数
    • 计算所有值的频率差值总和
    • 返回总和除以4的结果

这个解法的核心思想是将问题转化为频率平衡问题，利用交换操作的性质找到最优解。

代码实现

class Solution {
public:
    int minCost(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> cnt1, cnt2;
        
        for (int num : nums1) {
            cnt1[num]++;
        }
        for (int num : nums2) {
            cnt2[num]++;
        }
        
        set<int> allValues;
        for (int num : nums1) allValues.insert(num);
        for (int num : nums2) allValues.insert(num);
        
        int totalDiff = 0;
        for (int val : allValues) {
            int c1 = cnt1[val];
            int c2 = cnt2[val];
            if ((c1 + c2) % 2 != 0) {
                return -1;
            }
            totalDiff += abs(c1 - c2);
        }
        
        return totalDiff / 4;
    }
};

class Solution:
    def minCost(self, nums1: list[int], nums2: list[int]) -> int:
        from collections import Counter
        
        cnt1 = Counter(nums1)
        cnt2 = Counter(nums2)
        
        all_values = set(nums1) | set(nums2)
        
        total_diff = 0
        for val in all_values:
            c1 = cnt1[val]
            c2 = cnt2[val]
            if (c1 + c2) % 2 != 0:
                return -1
            total_diff += abs(c1 - c2)
        
        return total_diff // 4

public class Solution {
    public int MinCost(int[] nums1, int[] nums2) {
        var cnt1 = new Dictionary<int, int>();
        var cnt2 = new Dictionary<int, int>();
        
        foreach (int num in nums1) {
            cnt1[num] = cnt1.GetValueOrDefault(num, 0) + 1;
        }
        foreach (int num in nums2) {
            cnt2[num] = cnt2.GetValueOrDefault(num, 0) + 1;
        }
        
        var allValues = new HashSet<int>(nums1);
        foreach (int num in nums2) {
            allValues.Add(num);
        }
        
        int totalDiff = 0;
        foreach (int val in allValues) {
            int c1 = cnt1.GetValueOrDefault(val, 0);
            int c2 = cnt2.GetValueOrDefault(val, 0);
            if ((c1 + c2) % 2 != 0) {
                return -1;
            }
            totalDiff += Math.Abs(c1 - c2);
        }
        
        return totalDiff / 4;
    }
}

var minCost = function(nums1, nums2) {
    const cnt1 = new Map();
    const cnt2 = new Map();
    
    for (const num of nums1) {
        cnt1.set(num, (cnt1.get(num) || 0) + 1);
    }
    for (const num of nums2) {
        cnt2.set(num, (cnt2.get(num) || 0) + 1);
    }
    
    const allValues = new Set([...nums1, ...nums2]);
    
    let totalDiff = 0;
    for (const val of allValues) {
        const c1 = cnt1.get(val) || 0;
        const c2 = cnt2.get(val) || 0;
        if ((c1 + c2) % 2 !== 0) {
            return -1;
        }
        totalDiff += Math.abs(c1 - c2);
    }
    
    return Math.floor(totalDiff / 4);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(k)

其中 n 是数组长度，k 是不同元素的个数。