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

àì夳堔傛蜴生んèń 2023-10-06 22:36 31阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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;
        }
    }