3868. Minimum Cost to Equalize Arrays Using Swaps

📘 題目敘述

給你兩個長度為 n 的整數陣列 nums1 和 nums2。

你可以做以下兩種操作任意次：

• 在同一個陣列內交換：選兩個 index i 和 j，然後交換 nums1[i] 和 nums1[j]，或交換 nums2[i] 和 nums2[j]。這個操作免費
• 在兩個陣列之間交換：選一個 index i，交換 nums1[i] 和 nums2[i]。這個操作的花費是 1

請回傳讓 nums1 和 nums2 變成完全相同所需的最小花費。如果做不到，請回傳 -1。

條件限制

• 2 <= n == nums1.length == nums2.length <= 8 * 10^4
• 1 <= nums1[i], nums2[i] <= 8 * 10^4

🧠 解題思路

這題的關鍵是先不要去想每個位置怎麼換，而是先想：

最後如果 nums1 和 nums2 要變成一樣，那每個數字在兩個陣列中的總次數必須可以平均分掉。

因為同陣列內交換是免費的，所以陣列內部順序其實不重要。真正重要的是：

• 某個數字 i 在 nums1 出現幾次
• 某個數字 i 在 nums2 出現幾次

如果最後兩個陣列要相同，那對每個數字 i 而言：

• nums1 和 nums2 最後都要各拿到總次數的一半

所以如果某個數字的總次數：c1[i] + c2[i] 是奇數，那一定沒辦法平均分到兩邊，答案直接是 -1。

如果每個數字的總次數都是偶數，那就有機會做到。

接下來要想 cost。

如果某個數字在 nums1 比 nums2 多，代表它有一部分要被送去另一邊。而另一個數字可能剛好相反，在 nums2 比 nums1 多，也需要被送過來。

所以對每個數字，我們看：abs(c1[i] - c2[i])，這表示這個數字在兩邊的失衡量。

但這個值如果直接加起來，會重複算兩次，因為：

• 一個要送出去的數
• 一個要補進來的數

本來就是同一組調整的兩端。

而且一次跨陣列交換，會同時修正兩個元素，所以最後要除掉對應的重複計算。

這份程式最後得到的答案是：

• 把所有 abs(c1[i] - c2[i]) 加總
• 再除以 4

也就是最少需要幾次跨陣列交換。

核心原因是：

• 每個真正需要跨邊移動的元素，只佔 abs(c1[i] - c2[i]) / 2
• 而一次跨陣列交換會同時修正兩邊各一個元素
• 所以總和最後要除以 4

也就是說，這題的核心就是：

先檢查每個數字的總次數能不能平分，如果可以，再用兩邊次數差的總失衡量去算最少需要幾次跨陣列交換。

所有變數

• c1：map<int, int>，記錄每個數字在 nums1 中出現幾次
• c2：map<int, int>，記錄每個數字在 nums2 中出現幾次
• s：set<int>，存兩個陣列中出現過的所有數字
• ans：所有數字失衡量加總後的值，最後再轉成最少交換次數

🪜 主要流程步驟

1. 先統計兩個陣列中每個數字出現的次數

map<int, int> c1, c2;
set<int> s;
for (int x : nums1) {
    c1[x]++;
    s.insert(x);
}
for (int x : nums2) {
    c2[x]++;
    s.insert(x);
}

這一步是在做兩件事：

• c1[x] 記 x 在 nums1 出現幾次
• c2[x] 記 x 在 nums2 出現幾次

同時把所有出現過的數字放進 s，這樣後面只要掃 s，就能把所有可能的數字都檢查到。

2. 對每個出現過的數字，先檢查總次數是不是偶數

for (int i : s) {
    if ((c1[i] + c2[i]) % 2 == 1) {
        return -1;
    }

這一步是整題最重要的可行性判斷。

因為最後如果兩個陣列要完全相同，那某個數字 i 的總次數必須能平均分到兩邊。

所以：

• 如果 c1[i] + c2[i] 是奇數
• 就不可能一邊一半

這時不管怎麼交換都做不到，直接回傳 -1。

3. 如果可以平分，就把這個數字的失衡量加到 ans

ans += abs(c1[i] - c2[i]);

這裡是在算這個數字目前兩邊差多少。

例如：

• c1[i] = 5
• c2[i] = 1

那代表這個數字在 nums1 這邊多了很多，最後一定有一些要送到 nums2。

而 abs(c1[i] - c2[i]) 就是它目前的失衡程度。

把所有數字的失衡量加總起來，就能知道整體總共有多少「不平衡」。

4. 為什麼最後要除以 4

return ans / 4;

這是這題最容易卡住的地方。

先看一個數字 i：

• 如果 abs(c1[i] - c2[i]) = 2
• 代表它其實只需要有 1 個元素跨邊移動

所以每個數字真正需要移動的數量，其實是：abs(c1[i] - c2[i]) / 2

但如果你把所有數字的 abs(c1[i] - c2[i]) 加總起來，這個「要送出去」和「要補進來」兩邊都會被算到。

而一次跨陣列交換：

• 會從 nums1 送一個到 nums2
• 同時也從 nums2 送一個到 nums1

所以一次操作會同時解決兩個方向的需求。

因此最後總失衡量要除以：

• 先除 2：把差值轉成真正需要移動的元素數
• 再除 2：因為一次交換會同時解決兩邊

合起來就是除以 4。

5. 最後回傳最少跨陣列交換次數

當所有數字都檢查完後：

• 如果中間沒有遇到奇數總次數
• 就表示可以做到
• 而 ans / 4 就是最少需要幾次花費為 1 的跨陣列交換

同陣列內交換免費，所以不需要額外算進成本。

⏱️ 複雜度

設 n = nums1.length。

• 時間複雜度：O(n log n) 兩次掃描陣列時，map 和 set 的插入是 O(log n)，後面再掃一次所有不同數字。
• 空間複雜度：O(n) 額外使用了 c1、c2 和 s 來記錄次數與出現過的數字。

💻 程式碼實作

class Solution {
public:
    int minCost(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> c1, c2; // 次數
        set<int> s;           // 所有數字
        for (int x : nums1) {
            c1[x]++;
            s.insert(x);
        }
        for (int x : nums2) {
            c2[x]++;
            s.insert(x);
        }

        int ans = 0;
        for (int i : s) {
            if ((c1[i] + c2[i]) % 2 == 1) { // 奇數無法配對
                return -1;
            }
            ans += abs(c1[i] - c2[i]);
        }
        return ans / 4;
    }
};

🔗 題目連結

https://leetcode.com/problems/minimum-cost-to-equalize-arrays-using-swaps/