并查集
增删改查时间复杂度为O(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方法的代价越低越好
- 1)每个节点都有一条往上指的指针
- 2)节点a往.上找到的头节点，叫做a所在集合的代表节点
- 3)查询x和y是否属于同一个集合，就是看看找到的代表节点是不是一个
- 4)把x和y各自所在集合的所有点合并成一个集合，只需要小集合的代表点挂
在大集合的代表点的下方即可
并查集的优化
- 1)节点往上找代表点的过程，把沿途的链变成扁平的
- 2)小集合挂在大集合的下面
- 3)如果方法调用很频繁，那么单次调用的代价为O(1)，两个方法都如此
并查集的应用
- 解决两大块区域的合并问题
- 常用在图等领域中
并查集核心代码
package com.harrison.class10; import java.util.HashMap; import java.util.List; import java.util.Stack; public class Code01_UnionFind { public static class Node<V> { V value; public Node(V v) { value = v; } } public static class UnionFind<V> { public HashMap<V, Node<V>> nodes; public HashMap<Node<V>, Node<V>> parents; public HashMap<Node<V>, Integer> sizeMap; public UnionFind(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 boolean isSameSet(V a,V b) { return findFather(nodes.get(a))==findFather(nodes.get(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); } } public int sets() { return sizeMap.size(); } } }
【题目】
如果两个user，a字段一样、或者b字段一样、或者c字段一样，就认为是一个人。请合并users，返回合并之后的用户数量
package com.harrison.class10; import java.util.HashMap; import java.util.List; import java.util.Stack; public class Code02_MergeUsers { public static class User { public String a; public String b; public String c; public User(String a, String b, String c) { this.a = a; this.b = b; this.c = c; } } public static class Node<V> { V value; public Node(V v) { value = v; } } public static class UnionFind<V> { public HashMap<V, Node<V>> nodes; public HashMap<Node<V>, Node<V>> parents; public HashMap<Node<V>, Integer> sizeMap; public UnionFind(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 boolean isSameSet(V a, V b) { return findFather(nodes.get(a)) == findFather(nodes.get(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); } } public int getSizeNum() { return sizeMap.size(); } } // 如果两个user，a字段一样、或者b字段一样、或者c字段一样，就认为是一个人 // 请合并users，返回合并之后的用户数量 public static int mergeUsers(List<User> users) { UnionFind<User> unionFind = new UnionFind<>(users); HashMap<String, User> mapA = new HashMap<>(); HashMap<String, User> mapB = new HashMap<>(); HashMap<String, User> mapC = new HashMap<>(); for (User user : users) { if (mapA.containsKey(user.a)) { unionFind.union(user, mapA.get(user.a)); }else { mapA.put(user.a, user); } if (mapB.containsKey(user.b)) { unionFind.union(user, mapB.get(user.b)); }else { mapB.put(user.b, user); } if (mapC.containsKey(user.c)) { unionFind.union(user, mapC.get(user.c)); }else { mapC.put(user.c, user); } } //向并查集询问，合并之后，还有多少个集合 return unionFind.getSizeNum(); } }
