LeetCode_并查集_困难_765.情侣牵手-蒲公英云

LeetCode_并查集_困难_765.情侣牵手

1.题目

n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。

人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。

返回最少交换座位的次数，以便每对情侣可以并肩坐在一起。每次交换可选择任意两人，让他们站起来交换座位。

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

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

提示：
2n == row.length
2 <= n <= 30
n 是偶数
0 <= row[i] < 2n
row 中所有元素均无重复

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/couples-holding-hands

2.思路

（1）并查集

3.代码实现（Java）

//思路1————并查集
class Solution {
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        //给每对情侣分配一个couple_id
        UF uf = new UF(n);
        for (int i = 0; i < n; i += 2) {
            //将两人的 couple_id 进行连接(每对情侣的 ID 相邻，它们除以二向下取整之后结果相同)
            uf.union(row[i] / 2, row[i + 1] / 2);
        }
        //和连通分量的差即为需要交换的次数
        return n - uf.getCount();
    }
}
//并查集
class UF {
    //记录连通分量(树)的个数
    private int count;
    //节点 x 的根节点是 root[x]
    private int[] root;
    //记录每棵树中的节点数
    private int[] size;
    //初始化
    public UF(int n) {
        //初始时每个节点都是一个连通分量
        this.count = n;
        root = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            //初始时每个节点的根节点都是其自己
            root[i] = i;
            size[i] = 1;
        }
    }
    //将 p 和 q 连通
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) {
            // p 和 q 的根节点相同，它们本就是连通的，直接返回即可
            return;
        } else {
            /*
                p 和 q 的根节点不相同，将它们连通
                小树接到大树下面，这样比较平衡
            */
            if (size[rootP] > size[rootQ]) {
                root[rootQ] = rootP;
                size[rootP] += size[rootQ];
            } else {
                root[rootP] = rootQ;
                size[rootQ] += size[rootP];
            }
             count--;
        }
    }
    //判断 p 和 q 是否互相连通
    public boolean isConnected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        //如果 p 和 q 的根节点相同，则说明它们在同一颗树上，即它们是连通的
        return rootP == rootQ;
    }
    //查找节点 x 的根节点
    public int find(int x) {
        while (root[x] != x) {
            //进行路径压缩
            root[x] = root[root[x]];
            x = root[x];
        }
        return x;
    }
    //返回连通分量(树)的个数
    public int getCount() {
        return count;
    }
}