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. 1. 給定兩個等長數組nums、forbidden，長度為n。

2. 2. 操作：任意交換 nums 中兩個不同下標的元素，可以交換無數次。

3. 3. 目標：調整后每個位置 i 都滿足 nums[i] ≠ forbidden[i]，求最少交換次數；如果做不到，返回 -1。

4. 4. 示例：nums=[1,2,3]，forbidden=[3,2,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. 1.(沖突總數 k + 1) / 2：兩兩交換沖突位置，是最優的交換方式（一次交換解決兩個沖突）。

2. 2.沖突位置里重復數字的最大次數 mx：扎堆的沖突數字必須單獨處理，是硬性最低要求。

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

三、時間復雜度分析

整個算法只做了3次線性遍歷：

1. 1. 遍歷 nums 統計數字頻率 → O(n)

2. 2. 遍歷 forbidden 做無解判斷 + 統計沖突位置 + 統計重復數字 → O(n)

3. 3. 簡單數學計算 → O(1)

總時間復雜度：O(n)
（n 是數組長度，滿足題目 n ≤ 10? 的高效運行要求）

四、額外空間復雜度分析

算法只使用了**哈希表（字典）**存儲數字頻率：

• ? 哈希表最多存儲2n個不同數字（nums+forbidden），但實際遠小于這個值。

• ? 沒有使用遞歸、二維數組等額外空間。

總額外空間復雜度：O(n)

總結

1. 1. 解題四步：判斷無解 → 統計沖突位置 → 統計沖突數字最大值 → 計算最小交換；

2. 2. 時間復雜度：O(n)（線性時間，高效處理大數據）；

3. 3. 額外空間復雜度：O(n)（僅用哈希表存儲頻率）。

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助力您的未來發展。