什么是并查集
一种数据结构,用来描述集合。
- 查(find):某个元素是否属于某个集合
- 并(Combine):某个元素和另一个元素属于同一个集合
基本的场景:
假设用10个人,用大小为10的数组来表示,a[0] ~ a[9],数据的内容是下标
这十个人中间有互相认识的,互相认识的需要分成一组
比如 5,6 认识,5和6成为一组,这时a[5]的值变成了6,表示5,6已经是一组了
1,2认识,a[1]的值变成了2,这时1,2成为一组
2,3认识,因为1,2已经是一组了,将a[1],a[2]的下标改成3。这时1,2,3成为一组
1,4认识,这时1,2,3,4成为一组,a[1] = a[2] = a[3] = a[4]=4
1,5认识,这时1,2,3,4,5,6成为一组,a[1] = a[2] = a[3] = a[4] = a[5] = a[6] = 6
我们用树的结构重新表示下数据的结构
并查集有哪些操作呢
- unionElements():就是上面描述的朋友组队的过程(合并函数)
- find(x):我是属于那个队的,find(4)=6,说明4属于6队
- isConnected(x,y)判断两个人是否是一对,isConnected(2,3)=true,说明2和3是属于同一对
老套路,这时候改上代码look look了:
unionElements 方法:
public void unionElements(int firstElement, int secondElement) {
//找出firstElement所在的集合
int firstUnion = find(firstElement);
//找出secondElement所在的集合
int secondUnion = find(secondElement);
//如果这两个不是同一个集合,那么合并。
if (firstUnion != secondUnion) {
//遍历数组,使原来的firstUnion、secondUnion合并为secondUnion
for (int i = 0; i < this.size; i++) {
if (id[i] == firstUnion) {
id[i] = secondUnion;
}
}
}
}
find方法:
private int find(int element) {
return id[element];
}
isConnected方法:
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
上面是基本的并查集场景,我们先看看类似的LeetCode题目吧
朋友圈就是典型的交并集问题,求的是一共几个分组。
速度撸出代码瞧一瞧~
int[] p;
int[][] combines;
public int findCircleNum(int[][] M) {
combines = M;
int length = M.length;
p = new int[M.length];
// 构造初始化数组
for (int i = 0; i < length; i++) {
p[i] = i;
}
// combine函数合并
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
unionElements(i, j);
}
}
//统计组数
int res = 0;
for (int i = 0; i < M.length; i++) {
if (p[i] == i) {
res++;
}
}
return res;
}
private void unionElements(int i, int j) {
if (combines[i][j] == 1) {
int iP = find(i);
int jP = find(j);
//如果i所在的组和j所在的组不一致,合并两个组
if (iP != jP) {
for (int k = 0; k < p.length; k++) {
if(p[k] == iP) {
p[k] = jP;
}
}
}
}
}
private int find(int i) {
if (p[i] != i) {
return find(p[i]);
}
return p[i];
}
这道题不难,题目有点绕=。=,感觉LeetCode100分有20分考的是语文和概念理解。感觉是有了代码才编的题。。内核仍然是并查集,
构成树(全连通,无环)=》p数组的值相等,则构成树
多余边 =》发现p数组的两位是否连通,isConnected登场
“多个答案,返回,最后出现的边” =》说的就是让你遍历完
一顿组合拳,撸出答案
public class Solution {
int[] p;
public int[] findRehdundantConnection(int[][] edges) {
int[] result = new int[2];
// 构造初始化数组
p = new int[edges.length+1];
for (int i = 1; i < edges.length+1; i++) {
p[i] = i;
}
for (int i = 1; i < edges.length+1; i++) {
//判断成环
if (isConnected(edges[i-1][0], edges[i-1][1])) {
result[0] = edges[i-1][0];
result[1] = edges[i-1][1];
}
unionElements(edges[i-1][0], edges[i-1][1]);
}
return result;
}
private boolean isConnected(int i, int j) {
return find(i) == find(j);
}
private void unionElements(int i, int j) {
int iP = find(i);
int jP = find(j);
if (iP != jP) {
for (int k = 0; k < p.length; k++) {
if (p[k] == iP) {
p[k] = jP;
}
}
}
}
private int find(int i) {
if (p[i] != i) {
return find(p[i]);
}
return p[i];
}
}
介绍了并查集的基本用法,其实还有优化,路径缩短的算法。以后在讨论,等可信过了🙃=。=
PS:加油~今天看了《月亮与六便士》,以为是个理想主义的书,其实有毒。最后用王尔德的一句话结尾,“爱自己,是终身浪漫的开始”。
网友评论