Union_Find_总结

发表于 | 分类于 | 0 comments

Union-Find

这块非常建议去看下普林斯顿的算法课第一章的ppt，看完基本就懂了

Union-Find 的主要作用(在LeetCode 和遇到的OA中)主要可以用于找到联通区域，或者找到集合在一起的类。
通过Union-Find, 当数字不断加入的时候，可以按照顺序，将他们聚合在一起。

聚合的方式是int[son] = father, 对于son这个元素，他的值即是他指向的父亲节点。最终将会形成一个或者多个树结构的区块（树可能联通）

Union-Find 主要有两种方式构成，一种是Quick - Find，另一种是Quick - Union。这两种方法之间有trade-off，想要查找快，那么union这个过程可能较慢。想要union快，那么find就会较慢

Quick - Find

简而言之，就是查找快，这样形成的树一般深度为2，查找某个数，和其根很快。但是每次加入新节点的时候，需要的时间较长。

这个一般不常用，基本做题没遇到过

Quick - Union

一般都是用这个，然后再加入压缩路径的算法

典型题目

547. Friend Circles

305. Number of Islands II

通用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0) return 0;
        int m = M.length;
        int count = m;
        int[] union = new int[m];
        for (int i = 0; i < m; i++) union[i] = i;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (i == j) continue;
                if (M[i][j] == 1) {
                    int root = findUnion(union, j);
                    int rootself = findUnion(union, i);
                    union[rootself] = root;
                }
            }
        }
        
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < m; i++) {
            set.add(findUnion(union, i));
        }
        return set.size();
    }
    
    public int findUnion(int[] union, int id) {
        while (id != union[id]) {
            union[id] = union[union[id]];
            id = union[id];
        }
        return id;
    }
}

模板解释: 开始的时候，让所有节点的父亲节点指向自己

findUnion中，可以让每个节点的父亲，指向自己的爷爷，这样会使得最后形成的树更短，之后的搜索也会更快。