Hard

题目描述

给定两个长度相等为 n 的 0 索引整数数组 nums1 和 nums2。

在一次操作中，你可以交换 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。

示例 2：

输入：nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3]
输出：10

示例 3：

输入：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

解题思路

这是一个贪心算法问题，需要分步骤分析：

第一步：找出必须交换的位置 找出所有 nums1[i] == nums2[i] 的位置，这些位置必须通过交换来解决。

第二步：统计频次 统计这些相等位置中每个数值的出现次数。如果某个数值出现次数超过总相等位置数的一半，那么这个数值就是"主导数值"。

第三步：判断可行性

  • 如果没有主导数值，任意配对交换即可
  • 如果有主导数值，需要额外找一些位置来"稀释"它

第四步：寻找额外位置 对于有主导数值的情况，需要找到足够的位置 i，使得 nums1[i] != nums2[i] 且 nums1[i] 或 nums2[i] 不等于主导数值。这样可以通过交换来帮助解决主导数值的问题。

第五步：贪心选择 为了最小化成本，优先选择索引值较小的位置进行交换。

核心思想： 通过贪心策略，先处理必须交换的相等位置，再根据需要添加额外的交换位置，确保所有位置最终都不相等。

代码实现

class Solution {
public:
    long long minimumTotalCost(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        long long totalCost = 0;
        int swapCount = 0;
        unordered_map<int, int> freq;
        
        // 找出所有相等的位置
        for (int i = 0; i < n; i++) {
            if (nums1[i] == nums2[i]) {
                totalCost += i;
                swapCount++;
                freq[nums1[i]]++;
            }
        }
        
        // 找出主导数值
        int dominant = -1, dominantCount = 0;
        for (auto& p : freq) {
            if (p.second > dominantCount) {
                dominant = p.first;
                dominantCount = p.second;
            }
        }
        
        // 检查是否需要额外的交换位置
        int need = max(0, 2 * dominantCount - swapCount);
        
        // 寻找额外的交换位置
        for (int i = 0; i < n && need > 0; i++) {
            if (nums1[i] != nums2[i] && nums1[i] != dominant && nums2[i] != dominant) {
                totalCost += i;
                swapCount++;
                need -= 2;
            }
        }
        
        // 检查是否可能
        if (need > 0) return -1;
        
        return totalCost;
    }
};

class Solution:
    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        total_cost = 0
        swap_count = 0
        freq = {}
        
        # 找出所有相等的位置
        for i in range(n):
            if nums1[i] == nums2[i]:
                total_cost += i
                swap_count += 1
                freq[nums1[i]] = freq.get(nums1[i], 0) + 1
        
        # 找出主导数值
        dominant = -1
        dominant_count = 0
        for val, count in freq.items():
            if count > dominant_count:
                dominant = val
                dominant_count = count
        
        # 检查是否需要额外的交换位置
        need = max(0, 2 * dominant_count - swap_count)
        
        # 寻找额外的交换位置
        for i in range(n):
            if need <= 0:
                break
            if nums1[i] != nums2[i] and nums1[i] != dominant and nums2[i] != dominant:
                total_cost += i
                swap_count += 1
                need -= 2
        
        # 检查是否可能
        if need > 0:
            return -1
        
        return total_cost

public class Solution {
    public long MinimumTotalCost(int[] nums1, int[] nums2) {
        int n = nums1.Length;
        long totalCost = 0;
        int swapCount = 0;
        Dictionary<int, int> freq = new Dictionary<int, int>();
        
        // 找出所有相等的位置
        for (int i = 0; i < n; i++) {
            if (nums1[i] == nums2[i]) {
                totalCost += i;
                swapCount++;
                freq[nums1[i]] = freq.GetValueOrDefault(nums1[i], 0) + 1;
            }
        }
        
        // 找出主导数值
        int dominant = -1;
        int dominantCount = 0;
        foreach (var pair in freq) {
            if (pair.Value > dominantCount) {
                dominant = pair.Key;
                dominantCount = pair.Value;
            }
        }
        
        // 检查是否需要额外的交换位置
        int need = Math.Max(0, 2 * dominantCount - swapCount);
        
        // 寻找额外的交换位置
        for (int i = 0; i < n && need > 0; i++) {
            if (nums1[i] != nums2[i] && nums1[i] != dominant && nums2[i] != dominant) {
                totalCost += i;
                swapCount++;
                need -= 2;
            }
        }
        
        // 检查是否可能
        if (need > 0) return -1;
        
        return totalCost;
    }
}

var minimumTotalCost = function(nums1, nums2) {
    const n = nums1.length;
    let totalCost = 0;
    let swapCount = 0;
    const freq = new Map();
    
    // 找出所有相等的位置
    for (let i = 0; i < n; i++) {
        if (nums1[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
贪心算法O(n)O(n)
  • 时间复杂度：O(n)，需要遍历数组两次，第一次统计相等位置，第二次寻找额外位置
  • 空间复杂度：O(n)，使用哈希表存储数值频次，最坏情况下所有元素都不同