2026-05-03：避免禁用值的最小交换次数。用go语言，给定两个长度为 n 的整数数组 nums 和 forbidden。你需要通过反复执行交换操作来调整

2026-05-03：避免禁用值的最小交换次数。用go语言，给定两个长度为 n 的整数数组 nums 和 forbidden。你需要通过反复执行交换操作来调整 nums，使得对每个位置 i，都满足 nums[i] ≠ forbidden[i]。

交换操作的规则是：你可以任意次选择两个不同的下标 i 和 j，然后交换 nums[i] 和 nums[j] 的值。交换次数可以是零次。

目标是：在所有能满足“每个位置 i 的 nums[i 都不能等于 forbidden[i]”的调整方案中，找出所需交换次数的最小值；如果不存在任何办法能做到上述条件，则返回 -1。

1 <= n == nums.length == forbidden.length <= 100000。

1 <= nums[i], forbidden[i] <= 1000000000。

输入： nums = [1,2,3], forbidden = [3,2,1]。

输出： 1。

解释：

一种最优的交换方案：

选择 nums 中下标 i = 0 和 j = 1，交换它们，得到 nums = [2, 1, 3]。

交换完成后，对于每个下标 i，nums[i] 都不等于 forbidden[i]。

题目来自力扣3785。

解题过程+复杂度分析 一、先明确题目核心要求

1. 给定两个等长数组nums、forbidden，长度为n。

2. 操作：任意交换 nums 中两个不同下标的元素，可以交换无数次。

3. 目标：调整后每个位置 i 都满足 nums[i] ≠ forbidden[i]，求最少交换次数；如果做不到，返回 -1。

4. 示例：nums=[1,2,3]，forbidden=[3,2,1]→ 最少交换 1 次。

二、分步骤详细解题过程 步骤1：判断是否存在合法方案（无解判断）

我们首先要确定：能不能通过交换让所有位置都不冲突。
判断规则：
把nums里的所有数字 +forbidden里的所有数字合并统计每个数字的总出现次数。
如果有任何一个数字的总次数 > n→ 直接返回 -1（无解）。

原理：
数组总长度只有 n，每个位置最终只能放一个数字。如果某个数字总数超过 n，无论怎么放，必然有至少一个位置会和 forbidden[i] 冲突，所以无解。

步骤2：统计「天然冲突位置」数量

遍历每一个位置i：
如果原始 nums[i] == forbidden[i]→ 这个位置是冲突位置，我们把所有这样的位置总数记为k。

示例：
nums = [1,2,3]，forbidden = [3,2,1]
位置0：1≠3 → 不冲突
位置1：2==2 → 冲突
位置2：3≠1 → 不冲突
所以冲突总数k = 1。

步骤3：统计冲突位置中「重复数字的最大出现次数」

在所有冲突位置里，统计每个数字出现了多少次，找到出现次数最多的那个数字的次数，记为mx。

示例：
只有位置1是冲突位置，数字是 2 → 冲突位置里数字2出现1次 →mx = 1。

原理：
如果某个数字在冲突位置里扎堆出现，比如 5 个冲突位置全是数字3，那这些位置无法内部两两交换解决，必须用这个最大次数作为最低交换限制。

步骤4：计算最小交换次数

最终答案取两个值的最大值：

1.(冲突总数 k + 1) / 2：两两交换冲突位置，是最优的交换方式（一次交换解决两个冲突）。

2.冲突位置里重复数字的最大次数 mx：扎堆的冲突数字必须单独处理，是硬性最低要求。

示例计算：
k=1 → (1+1)/2 = 1
mx=1
最大值 = 1 → 答案就是 1，和题目输出一致。

三、时间复杂度分析

整个算法只做了3次线性遍历：

1. 遍历 nums 统计数字频率 → O(n)

2. 遍历 forbidden 做无解判断 + 统计冲突位置 + 统计重复数字 → O(n)

3. 简单数学计算 → O(1)

总时间复杂度：O(n)
（n 是数组长度，满足题目 n ≤ 10⁵ 的高效运行要求）

四、额外空间复杂度分析

算法只使用了**哈希表（字典）**存储数字频率：

• 哈希表最多存储2n个不同数字（nums+forbidden），但实际远小于这个值。

• 没有使用递归、二维数组等额外空间。

总额外空间复杂度：O(n)

总结

1. 解题四步：判断无解 → 统计冲突位置 → 统计冲突数字最大值 → 计算最小交换；

2. 时间复杂度：O(n)（线性时间，高效处理大数据）；

3. 额外空间复杂度：O(n)（仅用哈希表存储频率）。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func minSwaps(nums, forbidden []int)int {
    n := len(nums)
    total := map[int]int{}
    for _, x := range nums {
        total[x]++
    }

     cnt := map[int]int{}
    k, mx := 0, 0
    for i, x := range forbidden {
        total[x]++
        if total[x] > n {
            return-1
        }
        if x == nums[i] {
            k++
            cnt[x]++
            mx = max(mx, cnt[x])
        }
    }

     return max((k+1)/2, mx)
}

 func main() {
    nums := []int{1, 2, 3}
    forbidden := []int{3, 2, 1}
    result := minSwaps(nums, forbidden)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def minSwaps(nums, forbidden):
    n = len(nums)
    total = {}
    for x in nums:
        total[x] = total.get(x, 0) + 1

     cnt = {}
    k, mx = 0, 0
    for i, x in enumerate(forbidden):
        total[x] = total.get(x, 0) + 1
        if total[x] > n:
            return-1
        if x == nums[i]:
            k += 1
            cnt[x] = cnt.get(x, 0) + 1
            mx = max(mx, cnt[x])

     return max((k + 1) // 2, mx)

 def main():
    nums = [1, 2, 3]
    forbidden = [3, 2, 1]
    result = minSwaps(nums, forbidden)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

  

  


 using namespace std;

 int minSwaps(vector& nums, vector& forbidden) {
    int n = nums.size();
    unordered_map total;
    for (int x : nums) {
        total[x]++;
    }

     unordered_map cnt;
    int k = 0, mx = 0;
    for (int i = 0; i < forbidden.size(); i++) {
        int x = forbidden[i];
        total[x]++;
        if (total[x] > n) {
            return-1;
        }
        if (x == nums[i]) {
            k++;
            cnt[x]++;
            mx = max(mx, cnt[x]);
        }
    }

     return max((k + 1) / 2, mx);
}

 int main() {
    vector nums = {1, 2, 3};
    vector forbidden = {3, 2, 1};
    int result = minSwaps(nums, forbidden);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。