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

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完整代码如下：

packagemainimport("fmt")funcminSwaps(nums,forbidden[]int)int{n:=len(nums)total:=map[int]int{}for_,x:=rangenums{total[x]++}cnt:=map[int]int{}k,mx:=0,0fori,x:=rangeforbidden{total[x]++iftotal[x]>n{return-1}ifx==nums[i]{k++cnt[x]++mx=max(mx,cnt[x])}}returnmax((k+1)/2,mx)}funcmain(){nums:=[]int{1,2,3}forbidden:=[]int{3,2,1}result:=minSwaps(nums,forbidden)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defminSwaps(nums,forbidden):n=len(nums)total={}forxinnums:total[x]=total.get(x,0)+1cnt={}k,mx=0,0fori,xinenumerate(forbidden):total[x]=total.get(x,0)+1iftotal[x]>n:return-1ifx==nums[i]:k+=1cnt[x]=cnt.get(x,0)+1mx=max(mx,cnt[x])returnmax((k+1)//2,mx)defmain():nums=[1,2,3]forbidden=[3,2,1]result=minSwaps(nums,forbidden)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>#include<unordered_map>#include<algorithm>usingnamespacestd;intminSwaps(vector<int>&nums,vector<int>&forbidden){intn=nums.size();unordered_map<int,int>total;for(intx:nums){total[x]++;}unordered_map<int,int>cnt;intk=0,mx=0;for(inti=0;i<forbidden.size();i++){intx=forbidden[i];total[x]++;if(total[x]>n){return-1;}if(x==nums[i]){k++;cnt[x]++;mx=max(mx,cnt[x]);}}returnmax((k+1)/2,mx);}intmain(){vector<int>nums={1,2,3};vector<int>forbidden={3,2,1};intresult=minSwaps(nums,forbidden);cout<<result<<endl;return0;}