leetcode 并查集类型题目练习

心已赠人 2022-09-07 14:43 158阅读 0赞

## 一 、并查集解决的问题 ##

如下图所示，有ABCDEFGHIJKLM这些**元素**，每两个元素之间有一个**连接线**。  
通过并查集功能，就可以将每一个元素所属于的集合给划分出来，也就是下面的**蓝色圈子**。

简化问题后，对应的输入是：  
123456789  
112355678  
输出是：  
111155555

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70]

## 二、并查集实现 ##

### 1、 最慢的合并操作 O(n) ###

step1:黄色的线 表示 两个元素有连接，即 value\[A\] = value\[C\] = A，两个元素不相连，则有A = value\[A\] != value\[E\]。 构造函数isConnected函数。  
step2:同时还可以得到 value\[E\]=value\[C\], 于是在经过并查集后，有value\[E\]=value\[C\]=value\[A\]=A。  
经过上面的不断迭代后，最后属于同一个集合的元素都会有相同的值。得到A，G，K三个集合。

### 2、并查集快速合并 O(h) ###

将集合抽象成一颗树，每个节点指向父节点，其中根节点指向本身。  
在建立好树后，就可以通过查找树的根节点来进行并查集合并。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 1]

private int find(int p) { 
    	while (p != parent[p])  // 没有指向其自身，说明不是根节点
    		p = parent[p]; 
    	return p;
    }
    
    // 如果两个元素属于同一个集合的话，可以使其中一个节点的根节点指向另一个根节点。该操作时间复杂度为O(h)，h为树的高度。
    public void unionElements(int p, int q) {  
    	int pRoot = find(p);
    	int qRoot = find(q);
    	if (pRoot == qRoot)
    		return;
    	parent[pRoot] = qRoot; // 关键操作，通过该语句，可以修改两个元素之间的连接情况，简化并查集
    }

### 3、并查集排序的优化 ###

##### 3.1 优化树的高度 #####

在进行union(4,9)时，如果执行 “parent\[pRoot\] = qRoot;” 语句，就会将8节点连到9上面，树的深度就会变大，查询根节点的时间就会变长。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 3]  
解决办法：合并时候判断一下谁的叶子节点数量多，叶子节点少的向多的上面合并。如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 4]

##### 3.2 并查集rank优化 #####

对下图进行union(4,2) 合并  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 5]  
如果根据树的叶子节点进行向那边合并时，结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 6]  
这样子整个树的深度由原理的3变为4。依靠集合的 size 判断指向并不是完全正确的，更准确的是，根据两个集合层数，具体判断根节点的指向，层数少的集合根节点指向层数多的集合根节点，如下图所示，这就是基于 rank 的优化。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70]: /images/20220829/d56a3ffb35074e37a7d96d23199e64d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 1]: /images/20220829/253dc7aec35045e6aa5d086809292caf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 2]: /images/20220829/c5b7baf9219a4ac7bb39f8020d39d118.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 3]: /images/20220829/e72a8bdf58ce44258cc49217d2fdaf64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 4]: /images/20220829/bacf14f474754d3e8527daf426beec4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 5]: /images/20220829/680ec2f4fe3145a39cb1f3b618297b61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDgxMjEx_size_16_color_FFFFFF_t_70 6]: /images/20220829/3a5038a185eb467686a9883bc334fbf9.png