2026-05-03：避免禁用值的最小交換次數(shù)。用go語言，給定兩個長度為 n 的整數(shù)數(shù)組 nums 和 forbidden。你需要通過反復(fù)執(zhí)行交換操作來調(diào)整

2026-05-03：避免禁用值的最小交換次數(shù)。用go語言，給定兩個長度為 n 的整數(shù)數(shù)組 nums 和 forbidden。你需要通過反復(fù)執(zhí)行交換操作來調(diào)整 nums，使得對每個位置 i，都滿足 nums[i] ≠ forbidden[i]。

交換操作的規(guī)則是：你可以任意次選擇兩個不同的下標(biāo) i 和 j，然后交換 nums[i] 和 nums[j] 的值。交換次數(shù)可以是零次。

目標(biāo)是：在所有能滿足“每個位置 i 的 nums[i 都不能等于 forbidden[i]”的調(diào)整方案中，找出所需交換次數(shù)的最小值；如果不存在任何辦法能做到上述條件，則返回 -1。

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

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

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

輸出： 1。

解釋：

一種最優(yōu)的交換方案：

選擇 nums 中下標(biāo) i = 0 和 j = 1，交換它們，得到 nums = [2, 1, 3]。

交換完成后，對于每個下標(biāo) i，nums[i] 都不等于 forbidden[i]。

題目來自力扣3785。

解題過程+復(fù)雜度分析 一、先明確題目核心要求

1. 1. 給定兩個等長數(shù)組nums、forbidden，長度為n。

2. 2. 操作：任意交換 nums 中兩個不同下標(biāo)的元素，可以交換無數(shù)次。

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

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

我們首先要確定：能不能通過交換讓所有位置都不沖突。
判斷規(guī)則：
把nums里的所有數(shù)字 +forbidden里的所有數(shù)字合并統(tǒng)計每個數(shù)字的總出現(xiàn)次數(shù)。
如果有任何一個數(shù)字的總次數(shù) > n→ 直接返回 -1（無解）。

原理：
數(shù)組總長度只有 n，每個位置最終只能放一個數(shù)字。如果某個數(shù)字總數(shù)超過 n，無論怎么放，必然有至少一個位置會和 forbidden[i] 沖突，所以無解。

步驟2：統(tǒng)計「天然沖突位置」數(shù)量

遍歷每一個位置i：
如果原始 nums[i] == forbidden[i]→ 這個位置是沖突位置，我們把所有這樣的位置總數(shù)記為k。

示例：
nums = [1,2,3]，forbidden = [3,2,1]
位置0：1≠3 → 不沖突
位置1：2==2 → 沖突
位置2：3≠1 → 不沖突
所以沖突總數(shù)k = 1。

步驟3：統(tǒng)計沖突位置中「重復(fù)數(shù)字的最大出現(xiàn)次數(shù)」

在所有沖突位置里，統(tǒng)計每個數(shù)字出現(xiàn)了多少次，找到出現(xiàn)次數(shù)最多的那個數(shù)字的次數(shù)，記為mx。

示例：
只有位置1是沖突位置，數(shù)字是 2 → 沖突位置里數(shù)字2出現(xiàn)1次 →mx = 1。

原理：
如果某個數(shù)字在沖突位置里扎堆出現(xiàn)，比如 5 個沖突位置全是數(shù)字3，那這些位置無法內(nèi)部兩兩交換解決，必須用這個最大次數(shù)作為最低交換限制。

步驟4：計算最小交換次數(shù)

最終答案取兩個值的最大值：

1. 1.(沖突總數(shù) k + 1) / 2：兩兩交換沖突位置，是最優(yōu)的交換方式（一次交換解決兩個沖突）。

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

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

三、時間復(fù)雜度分析

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

1. 1. 遍歷 nums 統(tǒng)計數(shù)字頻率 → O(n)

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

3. 3. 簡單數(shù)學(xué)計算 → O(1)

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

四、額外空間復(fù)雜度分析

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

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

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

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

總結(jié)

1. 1. 解題四步：判斷無解 → 統(tǒng)計沖突位置 → 統(tǒng)計沖突數(shù)字最大值 → 計算最小交換；

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

3. 3. 額外空間復(fù)雜度：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科普文章、工具評測、提升效率的秘籍以及行業(yè)洞察。 歡迎關(guān)注“福大大架構(gòu)師每日一題”，發(fā)消息可獲得面試資料，讓AI助力您的未來發(fā)展。