765. 情侶牽手

思路

給定一個大小為 $n$ 個陣列，裡面擺放著 $0\sim{n-1}$ 的數字，現在，0,1是一對情侶，2,3是一對情侶，找出要將位置倆倆交換幾次，才能讓所有情侶都坐在彼此的隔壁？

假如現在的陣列是 $[6,0,8,9,1,7,3,4,5,2]$ 。
沒有滿足條件的情侶對有 $[0,1],[6,7],[2,3]$ 。
此時交換 $[6,1], [2,4]$ ，就能讓所有情侶在彼此隔壁，共交換兩次。

我們先為「情侶對」去編號。對於 $x$ 來說，它屬於第 $x/2$ 對情侶。
然後按照位置，將「情侶對」的編號合併到一個集合當中。
在一個集合當中，如果存在 $k$ 對情侶，就需要 $k-1$ 次交換，讓集合中的情侶都成對。
拿上面的例子來說，

• 前兩個位置 $[6,0]$ 分別對應第 3, 0 對情侶，將這兩個編號合併到相同集合。
• $[8,9]$ 對應相同編號 4 ，合併後保持原狀。
• $[1,7]$ 對應 0, 3, 合併到相同集合。
• $[3,4]$ 對應編號 1, 2，合併到相同集合
• $[5,2]$ 對應 2, 1, 合併到相同集合。 最後合併的集合為 $\{0,3\},\{1,2\},\{4\}$ ， 大小分別是 2, 2, 1, 因此最後答案是 $(2-1)+(2-1)+(1-1)=2$ 。

再舉一個例子： $[6,0,1,5,2,3,8,4,7,9]$ ，一共五對情侶。

• $[6,0]\to[3,0]$ 合併
• $[1,5]\to[0,2]$ 合併
• $[2,3]\to[1,1]$ 合併
• $[8,4]\to[4,2]$ 合併
• $[7,9]\to[3,4]$ 合併

最後合併的集合為 $\{0,2,3,4\},\{1\}$ ，
大小分別是 4, 1, 因此最後答案是 $(4-1)+(1-1)=3$ 。
第一個比較大的集合，對應到 $0\sim7$ 編號的人，交換次數為 3，
以下是實際交換的方式，用 0 去出走，拯救世界。

1. 交換 $[0, 7]$ ： $[6,\blue7,1,5,2,3,8,4,\blue0,9]$
2. 交換 $[0,8]$ ： $[6,7,1,5,2,3,\blue0,4,\blue8,9]$
3. 交換 $[0,5]$ ： $[6,7,1,\blue0,2,3,\blue5,4,8,9]$

每一次，0 都會為坐自己旁邊的人找到對象。
如果集合的大小為 $k$ ，那麼有 $k$ 對情侶沒有配對正確，此時就讓一個人出走拯救世界，
當拯救完 $k-1$ 對情侶時，自己也抵達了終點，配到了人，所以是 $k-1$ 次。

因此用並查集去合併這些集合，記錄這些集合的大小，比如現在有三個集合，
大小為 $a,b,c$ ，一共需要交換 $a+b+c-3$ 次，
而我們知道總共有 $n/2$ 對情侶，所以 $a+b+c=n/2$ 。
答案就是 $n/2-3$ ，3 代表集合的數量。

程式碼

並查集

class Solution {
private:
    static const int MX = 31;
    int parent[MX];
    int setCnt; // 紀錄一共有多少集合
    int find(int x) {
        if(x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if(rootX != rootY) {
            parent[rootX] = rootY;
            setCnt--; // 合併時更新集合數量
        }
    }
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        // 初始化並查集
        iota(parent, parent + n / 2, 0); 
        setCnt = n / 2;
        // 將兩兩「情侶對編號」合併
        for(int i = 0; i < n; i += 2) {
            unite(row[i] / 2, row[i + 1] / 2);
        }
        return n / 2 - setCnt;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$