765. 情侣牵手

N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。
人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。
这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
示例 1:

输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。

示例 2:

输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

题解

本题使用的数据结构是并查集，思想借鉴的是leetcode这位大佬。需要注意的是，对于n个人，构成n/2对情侣，其实就是n/2个不同的结点，因此我们并查集初始化的大小也为n/2。要判断两个人是否是情侣，只需比较row[i]/2是否相等，例如2，3是一对情侣。

    public int minSwapsCouples(int[] row) {
        int len = row.length;
        int N = len / 2;
        UnionFind unionFind = new UnionFind(N);
        for (int i = 0; i < len; i += 2) {
            unionFind.unite(row[i] / 2, row[i + 1] / 2);
        }
        return N - unionFind.getSetCount();
    }

并查集模板

    int[] parent;
    int[] size;
    int n;
    // 当前连通分量数目
    int setCount;

    public UnionFind(int n) {
        this.n = n;
        this.setCount = n;
        this.parent = new int[n];
        this.size = new int[n];
        Arrays.fill(size, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    public int findset(int x) {
        return parent[x] == x ? x : (parent[x] = findset(parent[x]));
    }

    public boolean unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            int temp = x;
            x = y;
            y = temp;
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }

    public boolean connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
    public int getSetCount(){
        return setCount;
    }
}

还有一种比较特殊的解法：异或。参考了异或解法。如果是同一对情侣，那么一方进行异或就可以变成另一方。如果不是一对情侣，那么就不能通过异或变成另一方。

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