并查集理论及常见面试题

冷不防 2024-04-08 12:56 176阅读 0赞

## 并查集理论及常见面试题 ##

### 1 并查集理论 ###

1）有若干个样本a、b、c、d…类型假设都是V  
2）在并查集中一开始认为每个样本都在单独的集合里  
3）用户可以在任何时候调用如下两个方法：

*  boolean isSameSet（V x， V y）：查询样本x和样本y是否属于一个集合
 *  void union（V x， V y）：把x和y各自所在集合的所有样本合并成一个集合

4）isSameSet和union方法的代价越低越好  
5）每个节点都有一条往上指的指针  
6）节点a往上找到的头节点，叫做a所在集合的代表节点  
7）查询x和y是否属于同一个集合，就是看看找到的代表节点是否是同一个  
8）把x和y各自所在集合的所有点合并成一个集合，只需要小集合的代表点挂在大集合的代表点的下方即可

### 2 并查集的优化及应用场景 ###

#### 2.1 并查集的优化 ####

1.  节点往上找代表节点的过程，把沿途的链变成扁平的
2.  小集合挂在大集合的下面
3.  如果方法调用很频繁，则有结论：单次调用的代价为O（1），两个方法都是如此

#### 2.2 应用场景 ####

*  解决两大块区域的合并问题
 *  图领域

### 3 并查的实现【哈希表】 ###

#### 3.1 定义节点类 ####

并查集中每个集合中的元素

//定义节点类[并差集中的组成部分]
    public static class Node<V>{
        
        private V value;
        public Node(V value){
        
            this.value = value;
        }
    }

#### 3.2 定义并查集类 ####

主要有三个属性：并查集中集合的所有元素、每个集合中元素所对应的父节点，每个节点所包含的子节点数

//并查集类
    public static class UnionFind<V>{
        
        //该节点下所对应的节点
        public HashMap<V, Node<V>> nodes;
        //该节点对应的父节点
        public HashMap<Node<V>, Node<V>> parents;
        //以该节点为集合，所包含的元素个数
        public HashMap<Node<V>, Integer> sizeMap;
    }

#### 3.3 findFather(Node cur)寻找该节点的父节点 ####

/**
      * 找到父节点【给你一个节点，请你往上到不能再往上，把代表节点返回】
      * @param cur
      * @return
      */
     public Node<V> findFather(Node<V> cur){
        
         Stack<Node<V>> path = new Stack<>();
         while(cur != parents.get(cur)){
        
             //只要当前节点不是该节点对应父节点,就一级一级往上找
             path.push(cur);
             cur = parents.get(cur);
         }
         while(!path.isEmpty()){
        
             //将沿途的链变成扁平的
             parents.put(path.pop(), cur);
         }
         return cur;
     }

#### 3.4 isSameSet(V a, V b)判断两个节点是否在同一个集合 ####

> 注意：集合中，默认元素值不重复

/**
      * 是否在一个集合
      * @param a
      * @param b
      * @return
      */
     public boolean isSameSet(V a, V b){
        
         //看是否是同一个代表节点
         return findFather(nodes.get(a)) == findFather(nodes.get(b));
     }

#### 3.5 union(V a, V b)聚合方法 ####

/**
     * 合并，聚合
     * @param a
     * @param b
     */
    public void union(V a, V b){
        
        Node<V> aHead = findFather(nodes.get(a));
        Node<V> bHead = findFather(nodes.get(b));
        if(aHead != bHead){
        
            //两个集合不再一块，小的主动合并大的【小的代表节点放在大的代表节点下面】
            int aSetSize = sizeMap.get(aHead);
            int bSetSize = sizeMap.get(bHead);
            Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
            Node<V> small = big == aHead ? bHead : aHead;
            //小的父节点事大的
            parents.put(small, big);
            sizeMap.put(big, aSetSize + bSetSize);
            sizeMap.remove(small);
        }
    }

#### 3.6 sets()集合中的所有节点数 ####

/**
      * 该并查集包含的所有节点数
      * @return
      */
     public int sets(){
        
         return sizeMap.size();
     }

#### 3.7 全部代码 ####

/**
     * 并查集【哈希表实现】
     */
    public class UnionFindDemo {
        
    
        //定义节点类[并差集中的组成部分]
        public static class Node<V> {
        
            private V value;
    
            public Node(V value) {
        
                this.value = value;
            }
        }
    
    
        //并查集类
        public static class UnionFind<V> {
        
            //该节点下所对应的节点
            public HashMap<V, Node<V>> nodes;
            //该节点对应的父节点
            public HashMap<Node<V>, Node<V>> parents;
            //以该节点为集合，所包含的元素个数
            public HashMap<Node<V>, Integer> sizeMap;
    
            /**
             * 找到父节点【给你一个节点，请你往上到不能再往上，把代表节点返回】
             *
             * @param cur
             * @return
             */
            public Node<V> findFather(Node<V> cur) {
        
                Stack<Node<V>> path = new Stack<>();
                while (cur != parents.get(cur)) {
        
                    //只要当前节点不是该节点对应父节点,就一级一级往上找
                    path.push(cur);
                    cur = parents.get(cur);
                }
                while (!path.isEmpty()) {
        
                    //将沿途的链变成扁平的
                    parents.put(path.pop(), cur);
                }
                return cur;
            }
    
            /**
             * 是否在一个集合
             *
             * @param a
             * @param b
             * @return
             */
            public boolean isSameSet(V a, V b) {
        
                //看是否是同一个代表节点
                return findFather(nodes.get(a)) == findFather(nodes.get(b));
            }
    
            /**
             * 合并，聚合
             *
             * @param a
             * @param b
             */
            public void union(V a, V b) {
        
                Node<V> aHead = findFather(nodes.get(a));
                Node<V> bHead = findFather(nodes.get(b));
                if (aHead != bHead) {
        
                    //两个集合不再一块，小的主动合并大的【小的代表节点放在大的代表节点下面】
                    int aSetSize = sizeMap.get(aHead);
                    int bSetSize = sizeMap.get(bHead);
                    Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
                    Node<V> small = big == aHead ? bHead : aHead;
                    //小的父节点事大的
                    parents.put(small, big);
                    sizeMap.put(big, aSetSize + bSetSize);
                    sizeMap.remove(small);
                }
            }
    
            /**
             * 该并查集包含的所有节点数
             *
             * @return
             */
            public int sets() {
        
                return sizeMap.size();
            }
        }
    
    }

### 4 面试常考题目（LeetCode） ###

#### 4.1 LeetCode - 541：省份数量（朋友圈的个数） ####

![在这里插入图片描述][db90ac02c5e045e3ac051d225493bf8a.png]

##### 4.1.1 思路： #####

因为如果1,2之间认识，那么2,1一定认识，所以利用并查集的时候只需要遍历右上部分即可

##### 4.1.2 代码： #####

//利用并查集求解
    class Solution {
        
        public static int findCircleNum(int[][] isConnected) {
        
            int N = isConnected.length;
            //为每列创建集合{0} {1} ... {N - 1}
            UnionFind unionFind = new UnionFind(N);
            for(int i = 0; i < N; ++i){
        
                for(int j = i + 1; j < N; ++j){
        
                    //互相认识【合并】
                    if(isConnected[i][j] == 1){
        
                        unionFind.union(i, j);
                    }
                }
            }
            //返回并查集中集合个数
            return unionFind.sets();
        }
        
        public static class UnionFind {
        
            //每个集合的代表节点
            private int[] parent;
            //每个集合中元素的个数
            private int[] size;
            //类比于栈【辅助】
            private int[] help;
            //并查集中集合的个数
            private int sizes;
            
            public UnionFind(int N){
        
                this.parent = new int[N];
                this.size = new int[N];
                this.sizes = N;
                //按照最大额度算
                this.help = new int[N];
                for(int i = 0; i < N; i++){
        
                    parent[i] = i;
                    //最开始只有它自己
                    size[i] = 1;
                }
            }
            
            //找该节点的代表节点【父亲节点】,并且铺平
            public int findFather(int cur){
        
                int index = 0;
                while(cur != parent[cur]){
        
                    help[index++] = cur;
                    cur = parent[cur];
                }
                //类比栈的操作【第一个index--：找到代表节点的下一个  第二个index--：依次往下遍历，将路径上的每一个节点的父都设为cur代表节点】
                for(index--; index >= 0; index--){
        
                    parent[help[index]] = cur;
                }
                return cur;
            }
            
            public void union(int i, int j){
        
                int head1 = findFather(i);
                int head2 = findFather(j);
                if(parent[head1] != parent[head2]){
        
                    if(size[head1] >= size[head2]){
        
                        //head1 大：head2主动合并
                        parent[head2] = parent[head1];
                        size[head1] += size[head2];
                    } else {
        
                        parent[head1] = parent[head2];
                        size[head2] += size[head1];
                    }
                    //每次合并完之后，size--
                    sizes--;
                }
            }
            
            public int sets(){
        
                return sizes;
            }
        }
    }

#### 4.2 LeetCode - 岛屿的最大面积 ####

![在这里插入图片描述][576ea3ca81fa40d6bf78ea5f6d14ad52.png]

##### 4.2.1 解法一：infect，感染法 #####

//方法一：感染法infect
    class Solution {
        
        public int numIslands(char[][] grid) {
        
            //岛屿数量
            int lands = 0;
            for(int i = 0; i < grid.length; ++i){
        
                for(int j = 0; j < grid[i].length; ++j){
        
                    //如果为1，则感染【上下左右】，感染后变成0
                    if(grid[i][j] == '1'){
        
                        lands++;
                        infect(grid, i, j);
                    }
                }
            }
            return lands;
        }
        //感染方法infect
        public void infect(char[][] grid, int i, int j){
        
            //边界条件【是否超出范围】或不满足条件
            if(i < 0 || i > grid.length - 1 || j < 0 || j > grid[0].length - 1 || grid[i][j] != '1'){
        
                return;
            }
            //感染之后
            grid[i][j] = '0';
            infect(grid, i - 1, j);
            infect(grid, i, j - 1);
            infect(grid, i, j + 1);
            infect(grid, i+1, j);
        }
    }

##### 4.2.2 解法二：利用并查集 #####

//并查集：将行列转换为角标
    class Solution {
        
        public int numIslands(char[][] board) {
        
            int row = board.length;
            int col = board[0].length;
            UnionFind unionFind = new UnionFind(board);
            //处理第一行
            for(int j = 1; j < col; j++){
        
                if(board[0][j-1] == '1' && board[0][j] == '1'){
        
                    unionFind.union(0, j-1, 0, j);
                }
            }
            //处理第一列
            for(int i = 1; i < row; i++){
        
                if(board[i-1][0] == '1' && board[i][0] == '1'){
        
                    unionFind.union(i-1, 0, i, 0);
                }
            }
            for(int i = 1; i < row; i++){
        
                for(int j = 1; j < col; j++){
        
                    if(board[i][j] == '1'){
        
                        if(board[i][j-1] == '1'){
        
                            unionFind.union(i, j-1, i,j);
                        }
                        if(board[i-1][j] == '1'){
        
                            unionFind.union(i-1, j, i, j);
                        }
                    }
                }
            }
            return unionFind.sets();
        }
        public static class UnionFind{
        
            //父节点
            private int[] parent;
            //每个节点的子节点
            private int[] size;
            //辅助数组，类比栈
            private int[] help;
            //列数
            private int col;
            //并查集中集合个数
            private int sizes;
            
            public UnionFind(char[][] board){
        
                col = board[0].length;
                sizes = 0;
                int row = board.length;
                int len = row * col;
                parent = new int[len];
                size = new int[len];
                help = new int[len];
                for(int r = 0; r < row; r++){
        
                    for(int c = 0; c < col; c++){
        
                        //只给有1的创建集合
                        if(board[r][c] == '1'){
        
                            int i = index(r, c);
                            parent[i] = i;
                            size[i] = 1;
                            sizes++;
                        }
                    }
                }
            }
            
            public int index(int r, int c){
        
                //注意col是不变的
                return r * col + c;
            }
            
            
            //原始位置 -> 下标
            public int findFather(int i){
        
                int index = 0;
                while(i != parent[i]){
        
                    help[index++] = i;
                    i = parent[i];
                }
                for(index--; index >= 0; index--){
        
                    parent[help[index]] = i;
                }
                return i;
            }
            
            
            public void union(int row1, int col1, int row2, int col2){
        
                int i1 = index(row1, col1);
                int i2 = index(row2, col2);
                int f1 = findFather(i1);
                int f2 = findFather(i2);
                if(f1 != f2){
        
                    if(size[f1] >= size[f2]){
        
                        parent[f2] = f1;
                        size[f1] += size[f2];
                    } else {
        
                        parent[f1] = f2;
                        size[f2] += size[f1];
                    }
                    sizes--;
                }
            }
                
            public int sets(){
        
                return sizes;
            }
        }
    }

> 拓展：也可以用一个类代替1，只要不重复就可以

部分代码如下：

public static class Dot {
        
    
    }
    
    
    public static class Node<V> {
        
    
    	V value;
    
    	public Node(V v) {
        
    		value = v;
    	}
    
    }
    
    public static class UnionFind1<V> {
        
    	public HashMap<V, Node<V>> nodes;
    	public HashMap<Node<V>, Node<V>> parents;
    	public HashMap<Node<V>, Integer> sizeMap;
    
    	public UnionFind1(List<V> values) {
        
    		nodes = new HashMap<>();
    		parents = new HashMap<>();
    		sizeMap = new HashMap<>();
    		for (V cur : values) {
        
    			Node<V> node = new Node<>(cur);
    			nodes.put(cur, node);
    			parents.put(node, node);
    			sizeMap.put(node, 1);
    		}
    	}
    
    	public Node<V> findFather(Node<V> cur) {
        
    		Stack<Node<V>> path = new Stack<>();
    		while (cur != parents.get(cur)) {
        
    			path.push(cur);
    			cur = parents.get(cur);
    		}
    		while (!path.isEmpty()) {
        
    			parents.put(path.pop(), cur);
    		}
    		return cur;
    	}
    
    	public void union(V a, V b) {
        
    		Node<V> aHead = findFather(nodes.get(a));
    		Node<V> bHead = findFather(nodes.get(b));
    		if (aHead != bHead) {
        
    			int aSetSize = sizeMap.get(aHead);
    			int bSetSize = sizeMap.get(bHead);
    			Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
    			Node<V> small = big == aHead ? bHead : aHead;
    			parents.put(small, big);
    			sizeMap.put(big, aSetSize + bSetSize);
    			sizeMap.remove(small);
    		}
    	}
    
    	public int sets() {
        
    		return sizeMap.size();
    	}
    
    }

#### 4.3 LeetCode 305 - 岛屿问题扩展 ####

> 给一个二维数组，\[\[2,3\], \[4,1\], \[5,6\]\],每次空降1，第一次让2,3位置变成1，第二次让4,1位置变成1，每次空降都应该返回一个结果（岛屿的数量），比如，空降三次，结果应为\[2,3,5\]

##### 4.3.1 定义并查集 #####

public static class UnionFind1 {
        
            private int[] parent;
            private int[] size;
            private int[] help;
            private final int row;
            private final int col;
            private int sets;
    
            public UnionFind1(int m, int n) {
        
                row = m;
                col = n;
                sets = 0;
                int len = row * col;
                parent = new int[len];
                size = new int[len];
                help = new int[len];
            }
     }

##### 4.3.2 定义映射下标index #####

/**
      * 映射下标【r*col+c】，注意是col
      * @param r
      * @param c
      * @return
      */
     private int index(int r, int c) {
        
         return r * col + c;
     }

##### 4.3.3 定义find找寻自己的代表节点（父节点） #####

/**
     * 找代表节点【父亲】
     * @param i
     * @return
     */
    private int find(int i) {
        
        int hi = 0;
        while (i != parent[i]) {
        
            help[hi++] = i;
            i = parent[i];
        }
        for (hi--; hi >= 0; hi--) {
        
            parent[help[hi]] = i;
        }
        return i;
    }

##### 4.3.4 定义合并方法 #####

/**
     * 合并
     * @param r1
     * @param c1
     * @param r2
     * @param c2
     */
    private void union(int r1, int c1, int r2, int c2) {
        
        if (r1 < 0 || r1 == row || r2 < 0 || r2 == row || c1 < 0 || c1 == col || c2 < 0 || c2 == col) {
        
            return;
        }
        int i1 = index(r1, c1);
        int i2 = index(r2, c2);
        if (size[i1] == 0 || size[i2] == 0) {
        
            return;
        }
        int f1 = find(i1);
        int f2 = find(i2);
        if (f1 != f2) {
        
            if (size[f1] >= size[f2]) {
        
                size[f1] += size[f2];
                parent[f2] = f1;
            } else {
        
                size[f2] += size[f1];
                parent[f1] = f2;
            }
            sets--;
        }
    }

##### 4.3.5 定义连接方法【在节点上下左右都去寻找，看能否合并】 #####

/**
     * 连接
     * @param r
     * @param c
     * @return
     */
    public int connect(int r, int c) {
        
        int index = index(r, c);
        //看该位置上是否已经空降过，如果没有，就初始化，如果有，直接返回
        if (size[index] == 0) {
        
            parent[index] = index;
            size[index] = 1;
            sets++;
            union(r - 1, c, r, c);
            union(r + 1, c, r, c);
            union(r, c - 1, r, c);
            union(r, c + 1, r, c);
        }
        return sets;
    }

##### 4.3.6 整体代码流程 #####

/**
     * 岛屿问题扩展[空降1]，动态生成，节约空间
     */
    public class NumberOfIsLandTwo {
        
        
        public static List<Integer> numIslands21(int m, int n, int[][] positions) {
        
            UnionFind1 uf = new UnionFind1(m, n);
            List<Integer> ans = new ArrayList<>();
            //对于每一次的空降1，都生成一个结果，并返回
            for (int[] position : positions) {
        
                ans.add(uf.connect(position[0], position[1]));
            }
            return ans;
        }
    
        public static class UnionFind1 {
        
            private int[] parent;
            private int[] size;
            private int[] help;
            private final int row;
            private final int col;
            private int sets;
    
            public UnionFind1(int m, int n) {
        
                row = m;
                col = n;
                sets = 0;
                int len = row * col;
                parent = new int[len];
                size = new int[len];
                help = new int[len];
            }
    
            /**
             * 映射下标【r*col+c】，注意是col
             * @param r
             * @param c
             * @return
             */
            private int index(int r, int c) {
        
                return r * col + c;
            }
    
            /**
             * 找代表节点【父亲】
             * @param i
             * @return
             */
            private int find(int i) {
        
                int hi = 0;
                while (i != parent[i]) {
        
                    help[hi++] = i;
                    i = parent[i];
                }
                for (hi--; hi >= 0; hi--) {
        
                    parent[help[hi]] = i;
                }
                return i;
            }
    
            /**
             * 合并
             * @param r1
             * @param c1
             * @param r2
             * @param c2
             */
            private void union(int r1, int c1, int r2, int c2) {
        
                if (r1 < 0 || r1 == row || r2 < 0 || r2 == row || c1 < 0 || c1 == col || c2 < 0 || c2 == col) {
        
                    return;
                }
                int i1 = index(r1, c1);
                int i2 = index(r2, c2);
                if (size[i1] == 0 || size[i2] == 0) {
        
                    return;
                }
                int f1 = find(i1);
                int f2 = find(i2);
                if (f1 != f2) {
        
                    if (size[f1] >= size[f2]) {
        
                        size[f1] += size[f2];
                        parent[f2] = f1;
                    } else {
        
                        size[f2] += size[f1];
                        parent[f1] = f2;
                    }
                    sets--;
                }
            }
    
            /**
             * 连接
             * @param r
             * @param c
             * @return
             */
            public int connect(int r, int c) {
        
                int index = index(r, c);
                //看该位置上是否已经空降过，如果没有，就初始化，如果有，直接返回
                if (size[index] == 0) {
        
                    parent[index] = index;
                    size[index] = 1;
                    sets++;
                    union(r - 1, c, r, c);
                    union(r + 1, c, r, c);
                    union(r, c - 1, r, c);
                    union(r, c + 1, r, c);
                }
                return sets;
            }
    
        }
    }

注意：如果matrix极大，设计一种可行的并行计算方案  
思路：  
使用字符串，例如:“17\_41239491374”  
核心代码：

public int connect(int r, int c) {
        
    	String key = String.valueOf(r) + "_" + String.valueOf(c);
    	if (!parent.containsKey(key)) {
        
    		parent.put(key, key);
    		size.put(key, 1);
    		sets++;
    		String up = String.valueOf(r - 1) + "_" + String.valueOf(c);
    		String down = String.valueOf(r + 1) + "_" + String.valueOf(c);
    		String left = String.valueOf(r) + "_" + String.valueOf(c - 1);
    		String right = String.valueOf(r) + "_" + String.valueOf(c + 1);
    		union(up, key);
    		union(down, key);
    		union(left, key);
    		union(right, key);
    	}
    	return sets;
    }

[db90ac02c5e045e3ac051d225493bf8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/fc2f21f975954e44b43a0751fc11f212.png
[576ea3ca81fa40d6bf78ea5f6d14ad52.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/628da1d62ab84a228ee8df6a81ec5e33.png