765. Couples Holding Hands

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples' initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:

Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.

Note:

len(row) is even and in the range of [4, 60].
row is guaranteed to be a permutation of 0...len(row)-1.

https://leetcode.com/problems/couples-holding-hands/discuss/117520/Java-union-find-easy-to-understand-5-ms

class Solution {
    class UF {
        int[] parent;
        int count;
        public UF(int n) {
            parent = new int[n];
            count = n;
            for(int i = 0; i < n; i++) parent[i] = i;
        }
        
        public int find(int x) {
            if(x != parent[x]) x = find(parent[x]);
            return x;
        }
        public void union(int a, int b) {
            int ap = find(a);
            int bp = find(b);
            if(ap != bp) {
                count--;
                parent[ap] = bp;
            }
        }
    }
    public int minSwapsCouples(int[] row) {
        int n = row.length / 2;
        UF uf = new UF(n);
        for(int i = 0; i < n; i++) {
            int a = row[2 * i] / 2;
            int b = row[2 * i + 1] / 2;
            uf.union(a, b);
        }
        return n - uf.count;
    }
}

居然是个union find！

理解一下：每一对couple在union里面代表的数相同，都是nums[2*i] / 2, nums[2 * i + 1] / 2, 比如【0，1，2，3，4，5】对应的就是【0，0，1，1，2，2】

然后我们初始化之后，设置一个count参数，代表不需要换位置的couple数，初始是2n/2 = n。

然后对每一对潜在的couple（我们先假设他们是），比如【0，3，2，1】，我们对0，3来说，在union他就是0，1，然后他们parent不相等，说明需要交换一次，交换后把0指向1或者1指向0都可以，然后count--。

这样我们到了2，1，在union中他是1，0.这时因为他们的parent已经相同，所以我们就不用union了，count也不用--。所以最后答案就是n - count = 2 - 1 = 1交换一次。

同理对【0，5，1，3，2，4】，表示为【0，2，0，1，1，2】。

0先指向2，count--，

然后2指向1，count--，

最后到1，2的时候他们parent又相同了！所以答案是n - count = 3 - 1 = 2，交换两次。

class Solution {
    public int minSwapsCouples(int[] row) {
        int res = 0, n = row.length;
        for (int i = 0; i < n; i += 2) {
            if (row[i + 1] == (row[i] ^ 1)) continue;
            ++res;
            for (int j = i + 1; j < n; ++j) {
                if (row[j] == (row[i] ^ 1)) {
                    row[j] = row[i + 1];
                    row[i + 1] = row[i] ^ 1;
                    break;
                }
            }
        }
        return res;
    }
}

这是greedy的做法，对每一对不成双成对的，我们直接交换，把它的对应数接过来。

https://www.cnblogs.com/grandyang/p/8716597.html