美文网首页
LeetCode刷题指北---并查集

LeetCode刷题指北---并查集

作者: GableKing黑暗中漫舞 | 来源:发表于2020-03-31 00:45 被阅读0次

    什么是并查集

    一种数据结构,用来描述集合。

    • (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:加油~今天看了《月亮与六便士》,以为是个理想主义的书,其实有毒。最后用王尔德的一句话结尾,“爱自己,是终身浪漫的开始”。

    相关文章

      网友评论

          本文标题:LeetCode刷题指北---并查集

          本文链接:https://www.haomeiwen.com/subject/mvpbuhtx.html