Hard

题目描述

给你两个长度为 n 的整数数组 nums 和 forbidden。

你可以执行以下操作任意次数（包括零次）：

  • 选择两个不同的下标 i 和 j，交换 nums[i] 和 nums[j]。

返回使得对于每个下标 i，nums[i] 的值都不等于 forbidden[i] 所需的最小交换次数。如果无论进行多少次交换都无法确保每个下标都避免其禁止值，则返回 -1。

示例 1：

输入：nums = [1,2,3], forbidden = [3,2,1]
输出：1
解释：
一种最优的交换方案：
- 选择下标 i = 0 和 j = 1 交换，得到 nums = [2, 1, 3]。
- 交换后，对于每个下标 i，nums[i] 都不等于 forbidden[i]。

示例 2：

输入：nums = [4,6,6,5], forbidden = [4,6,5,5]
输出：2
解释：
一种最优的交换方案：
- 选择下标 i = 0 和 j = 2 交换，得到 nums = [6, 6, 4, 5]。
- 选择下标 i = 1 和 j = 3 交换，得到 nums = [6, 5, 4, 6]。
- 交换后，对于每个下标 i，nums[i] 都不等于 forbidden[i]。

示例 3：

输入：nums = [7,7], forbidden = [8,7]
输出：-1
解释：
无法让所有下标 i 的 nums[i] 都不等于 forbidden[i]。

示例 4：

输入：nums = [1,2], forbidden = [2,1]
输出：0
解释：
不需要交换，因为对于所有下标 i，nums[i] 已经不等于 forbidden[i]，所以答案是 0。

约束条件：

  • 1 <= n == nums.length == forbidden.length <= 10^5
  • 1 <= nums[i], forbidden[i] <= 10^9

解题思路

这是一个贪心算法问题，关键在于理解交换的本质和找到最优策略。

核心思路：

  1. 判断不可能的情况：首先统计 nums 和 forbidden 中所有值的总频次。如果某个值的总频次超过 n，说明即使把所有该值都放在 nums 中，也会有位置无法避免与 forbidden 中的该值重复，此时返回 -1。

  2. 识别冲突位置：找出所有 nums[i] == forbidden[i] 的位置，这些是需要通过交换来解决的"坏位置"。

  3. 贪心策略：

    • 统计每个值对应的坏位置数量
    • 总坏位置数为 badPairsSum
    • 单个值的最大坏位置数为 maxBadPairs

  4. 最小交换次数计算：

    • 理论上，每次交换最多能解决 2 个坏位置（如果两个位置都是坏的且可以互相解决）
    • 但对于同一个值的多个坏位置，需要额外的交换来打散它们
    • 因此答案是 max(⌈badPairsSum/2⌉, maxBadPairs)

这个公式的含义是：要么按照总坏位置数的一半来交换，要么按照最大单值坏位置数来交换，取较大值。

代码实现

class Solution {
public:
    int minSwaps(vector<int>& nums, vector<int>& forbidden) {
        int n = nums.size();
        unordered_map<int, int> freq;
        
        // 统计所有值的频次
        for (int i = 0; i < n; i++) {
            freq[nums[i]]++;
            freq[forbidden[i]]++;
        }
        
        // 检查是否存在不可能的情况
        for (auto& p : freq) {
            if (p.second >= n + 1) {
                return -1;
            }
        }
        
        // 统计坏位置
        unordered_map<int, int> badPairs;
        int badPairsSum = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == forbidden[i]) {
                badPairs[nums[i]]++;
                badPairsSum++;
            }
        }
        
        // 找到最大的单值坏位置数
        int maxBadPairs = 0;
        for (auto& p : badPairs) {
            maxBadPairs = max(maxBadPairs, p.second);
        }
        
        return max((badPairsSum + 1) / 2, maxBadPairs);
    }
};

class Solution:
    def minSwaps(self, nums: List[int], forbidden: List[int]) -> int:
        n = len(nums)
        freq = {}
        
        # 统计所有值的频次
        for i in range(n):
            freq[nums[i]] = freq.get(nums[i], 0) + 1
            freq[forbidden[i]] = freq.get(forbidden[i], 0) + 1
        
        # 检查是否存在不可能的情况
        for val, count in freq.items():
            if count >= n + 1:
                return -1
        
        # 统计坏位置
        bad_pairs = {}
        bad_pairs_sum = 0
        
        for i in range(n):
            if nums[i] == forbidden[i]:
                bad_pairs[nums[i]] = bad_pairs.get(nums[i], 0) + 1
                bad_pairs_sum += 1
        
        # 找到最大的单值坏位置数
        max_bad_pairs = max(bad_pairs.values()) if bad_pairs else 0
        
        return max((bad_pairs_sum + 1) // 2, max_bad_pairs)

public class Solution {
    public int MinSwaps(int[] nums, int[] forbidden) {
        int n = nums.Length;
        Dictionary<int, int> freq = new Dictionary<int, int>();
        
        // 统计所有值的频次
        for (int i = 0; i < n; i++) {
            freq[nums[i]] = freq.GetValueOrDefault(nums[i], 0) + 1;
            freq[forbidden[i]] = freq.GetValueOrDefault(forbidden[i], 0) + 1;
        }
        
        // 检查是否存在不可能的情况
        foreach (var kvp in freq) {
            if (kvp.Value >= n + 1) {
                return -1;
            }
        }
        
        // 统计坏位置
        Dictionary<int, int> badPairs = new Dictionary<int, int>();
        int badPairsSum = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == forbidden[i]) {
                badPairs[nums[i]] = badPairs.GetValueOrDefault(nums[i], 0) + 1;
                badPairsSum++;
            }
        }
        
        // 找到最大的单值坏位置数
        int maxBadPairs = 0;
        foreach (var kvp in badPairs) {
            maxBadPairs = Math.Max(maxBadPairs, kvp.Value);
        }
        
        return Math.Max((badPairsSum + 1) / 2, maxBadPairs);
    }
}

/**
 * @param {number[]} nums
 * @param {number[]} forbidden
 * @return {number}
 */
var minSwaps = function(nums, forbidden) {
    const n = nums.length;
    const freq = new Map();
    
    // 统计所有值的频次
    for (let i = 0; i < n; i++) {
        freq.set(nums[i], (freq.get(nums[i]) || 0) + 1);
        freq.set(forbidden[i], (freq.get(forbidden[i]) || 0) + 1);
    }
    
    // 检查是否存在不可能的情况
    for (const [val, count] of freq) {
        if (count >= n + 1) {
            return -1;
        }
    }
    
    // 统计坏位置
    const badPairs = new Map();
    let badPairsSum = 0;
    
    for (let i = 0; i < n; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

说明：

  • 时间复杂度：需要遍历数组统计频次和坏位置，每个操作都是 O(n)
  • 空间复杂度：使用哈希表存储频次和坏位置信息，最坏情况下存储 O(n) 个不同的值