《算法系列》之并查集

简介

  并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受。即使在空间上勉强通过，运行的时间复杂度也极高，只能用并查集来描述。故并查集是一种树型的数据结构，可用于处理一些不相交集合（disjoint sets）的合并及查询问题。

理论基础

  并查集（Union-find Data Structure）是一种树型的数据结构。它的特点是由子结点找到父亲结点，用于处理一些不交集（Disjoint Sets）的合并及查询问题。并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根节点，就能确定它在哪个集合里。 并查集跟树有些类似，只不过它和树是相反的。在树这个数据结构里面，每个节点会记录它的子节点。而在并查集里，每个节点只会记录它的父节点。

• 并（Union）：将两个子集合并成同一个集合。
• 查（Find）：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
• 集（Set）：代表这是一个以字典为基础的数据结构，它的基本功能是合并集合中的元素，查找集合中的元素。

并查集的代码实现：

class UnionFind {
    private Map father;
    
    public UnionFind() {
        father = new HashMap();
    }
    
    public void add(int x) {
        if (!father.containsKey(x)) {
            father.put(x, null);
        }
    }
    
    public void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY){
            father.put(rootX,rootY);
        }
    }
    
    public int find(int x) {
        int root = x;
        
        while(father.get(root) != null){
            root = father.get(root);
        }
        
        while(x != root){
            int original_father = father.get(x);
            father.put(x,root);
            x = original_father;
        }
        
        return root;
    }
    
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
} 
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
35
36
37
38
39
40
41
42

解题心得

• 前300道题里没多少关于并查集的题，但我们仍需要了解该解题方法。
• 很多题，并查集并不是最优解法，但了解并查集解法会给人眼前一亮的感觉。
• 只要找到了某个元素的的树根节点，就能确定它在哪个集合里。
• 并查集的典型应用是有关连通分量的问题。
• 并查集解决单个问题（添加，合并，查找）的时间复杂度都是O(1)。

算法题目

128. 最长连续序列

题目解析：建立一个并查集UF对象，用map存储，并用head指向共同的头结点，只有当head为空的时候其中size才有意义。
代码如下：

/**
 * 并查集
 */
class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length==0) return 0;
        int max=1;
        Map map = new HashMap<>();
        for(int i : nums){
            if(map.containsKey(i)) continue;
            if(!map.containsKey(i)){
                map.put(i,new UF(null,1));
            }
            if(map.containsKey(i+1)){
                UF head = map.get(i+1);
                int size = ++head.size;
                max=Math.max(size,max);
                UF item=new UF(null,size);
                head.head=item;
                map.put(i,item);
            }
            if(map.containsKey(i-1)){
                UF head = map.get(i-1);
                while(head.head!=null){
                    head=head.head;
                }
                head.size=map.get(i).size+head.size;
                max=Math.max(head.size,max);
                map.get(i).head=head;
            }
        }
        return max;

    }
}

class UF{
    public UF head;
    public int size;
    public UF (UF head , int size ){
        this.head=head;
        this.size=size;
    }
}
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
35
36
37
38
39
40
41
42
43
44

130. 被围绕的区域

题目解析：使用Union-Find法，先将四条边的’O’和dummy连接 --> 内部的’O’都与之四个邻居的’O’连接。最后不和dummy连接的’O’都是要修改为’X’的位置，修改即可。
代码如下：

/**
 * 并查集
 */
class Solution {
    public void solve(char[][] board) {
        // 注意二维数组的坐标[i,j]换算成一个数:i*n+j
        int m = board.length;
        int n = board[0].length;
        UF uf = new UF(m*n+1);
        // 最后一个位置留给dummy用
        int dummy = m*n;
        for(int i=0;i