当前位置:   article > 正文

Java 实现并查集查询、合并_java实现并查集

java实现并查集

前言

【题目描述】
给定一个没有重复值的整型数组 arr,初始时认为 arr 中每一个数各自都是一个单独的集合。
请设计一种叫 UnionFind 的结构,并提供以下两个操作。
1)boolean isSameSet(int a, int b):查询 a 和 b 这两个数是否属于一个集合。
2)void union(int a, int b):把 a 所在的集合与 b 所在的集合合并在一起,原本两个集合各自的元素以后都算作同一个集合。

【要求】
如果调用 isSameSet 和 union 的总次数逼近或超过 O(N),请做到单次调用 isSameSet 或 union
方法的平均时间复杂度为 O(1)。

思路

  1. 一开始每个元素自己形成单独的集合,同时其父结点指向自己【这里父结点为当前集合的根结点】;
    自成集合
  2. 定义查找集合根结点的方法,依次查找father结点,查找过程中将路过的所有结点都直接挂到根结点上,压缩查询路径,降低查询时间复杂度;

查询集合根结点

  1. 判断两个元素是否处于同一集合,即查询两个元素对应集合的根结点是否一致即可;
  2. 合并两个集合遵守如下原则:
    a.如果两个集合根结点一致,则说明属于同一个集合,无须进行合并操作;
    b.如果两个集合根结点不一致,则需要进行合并操作,将集合个数少的集合合并到集合个数多的集合【本质目的还是降低查找集合根结点层级,如下图查找结点2,如果以集合少的4为根结点,则查找层级+1】,如下图:
    合并集合

代码实现

  • 定义结点类Node;
    private static class Node<V> {
        private V value;

        public Node(V value) {
            this.value = value;
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 实现并查集类UnionFindSet;
 public static class UnionFindSet<V> {
        /**
         * V -> Node 关系映射
         */
        private HashMap<V, Node<V>> elementMap;
        /**
         * 存储Node以及其集合根结点
         */
        private HashMap<Node<V>, Node<V>> fatherMap;
        /**
         * 存储集合根结点元素 以及其集合元素数量
         */
        private HashMap<Node<V>, Integer> sizeMap;

        public UnionFindSet(List<V> list) {
            elementMap = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            makeSet(list);
        }

        private void makeSet(List<V> list) {
            for (V v : list) {
                Node node = new Node(v);
                elementMap.put(v, node);
                fatherMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        /**
         * 递归查找一个Node对应的头结点
         *
         * @return
         */
        private Node findHead(Node node) {
            if (node == null) {
                return null;
            }
            Node father = fatherMap.get(node);
            if (father != node) {
                father = findHead(father);
            }
            //将当前结点直接挂接到头结点上,降低层级
            fatherMap.put(node, father);
            return father;
        }

        /**
         * 查找两个结点是否处于同一集合
         *
         * @param a 结点a
         * @param b 结点b
         * @return
         */
        public boolean isSameSet(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
            }
            return false;
        }

        /**
         * 合并两个集合
         *
         * @param a
         * @param b
         */
        public void union(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                Node aHead = findHead(elementMap.get(a));
                Node bHead = findHead(elementMap.get(b));
                //两者头结点相同,不需要合并
                if (aHead == bHead) {
                    return;
                }
                int aSize = sizeMap.get(aHead);
                int bSize = sizeMap.get(bHead);
                //将结点数少的挂在结点数多的上面
                if (aSize <= bSize) {
                    fatherMap.put(aHead, bHead);
                    sizeMap.put(bHead, aSize + bSize);
                } else {
                    fatherMap.put(bHead, aHead);
                    sizeMap.put(aHead, aSize + bSize);
                }
            }

        }

    }
  • 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
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91

测试用例

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        UnionFindSet set = new UnionFindSet(list);
        set.union(1, 3);
        set.union(2, 4);

        boolean sameSet1 = set.isSameSet(2, 3);
        boolean sameSet2 = set.isSameSet(2, 4);
        System.out.println(sameSet1);
        System.out.println(sameSet2);

    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
输出结果
false
true
  • 1
  • 2

结语

如果以上文章对您有一点点帮助,希望您不要吝啬的点个赞加个关注,您每一次小小的举动都是我坚持写作的不懈动力!ღ( ´・ᴗ・` )

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/人工智能uu/article/detail/777393
推荐阅读
相关标签
  

闽ICP备14008679号