想要精通算法和SQL的成长之路 - 最长连续序列
- 前言
- 一. 最长连续序列
- 1.1 并查集数据结构创建
- 1.2 find 查找
- 1.3 union 合并操作
- 1.4 最终代码
前言
想要精通算法和SQL的成长之路 - 系列导航
并查集的运用
一. 最长连续序列
原题链接
这个题目,如何使用并查集是一个小难点,我们可以这么想:
- 对于数组中的每一个元素,在初始化的时候,根节点是它本身。以它为根节点的最长连续序列是1。
- 在经历过一系列的合并操作之后,以示例1来说,元素4的根节点就是元素1。
- 那么我们合并操作,合并的对象是谁?注意题目要求的是连续序列。那么针对每个元素num,我进行
union(num,num+1)
即可。 - 由于题目要求的是最长的连续序列,因此我们可以在并查集中维护一个
max
最大值。在合并操作的时候更新它。 - 由于数组内元素的跳跃性,我们可以用一个
HashMap
替代并查集的int[]
数组。
1.1 并查集数据结构创建
class UnionFind {private Map<Integer, Integer> parent;private Map<Integer, Integer> rank;private int max;public UnionFind(int[] nums) {max = 1;HashMap<Integer, Integer> tmpParent = new HashMap<>();HashMap<Integer, Integer> tmpRank = new HashMap<>();// 初始化操作:每个元素的根节点是它本身。并且以该元素作为根节点时的最长连续序列长度是1for (int num : nums) {tmpParent.put(num, num);tmpRank.put(num, 1);}parent = tmpParent;rank = tmpRank;}
}
1.2 find 查找
因为我们在合并过程中,进行union(num,num+1)
操作,以nums = [100,4,200,1,3,2]
为例,那么100+1 = 101,101这个元素是否在集合当中呢?
我们看下常规的函数:
public int find(int x) {while (x != parent[x]) {x = parent[x];}return x;
}
而我们在本题当中,使用HashMap
作为替换存储,同时我们还需要考虑到对象不存在的情况,代码如下
public int find(int x) {// 因为我们是以每个元素 + 1 来合并的,因此+1后的元素不一定存在于集合当中。// 这里就要特判,否则就会导致NPE,null和int进行 == 比较,会NPEif (!parent.containsKey(x)) {return x;}if (parent.get(x) == x) {return x;}parent.put(x, find(parent.get(x)));return parent.get(x);
}
1.3 union 合并操作
public void union(int x, int y) {// 如果不存在,也要直接返回if (!parent.containsKey(y)) {return;}int rootX = find(x);int rootY = find(y);// 是同一个根节点,直接返回if (rootX == rootY) {return;}// 区间合并,算出合并后的连续序列长度int tmpSum = rank.get(rootY) + rank.get(rootX);if (rank.get(rootX) > rank.get(rootY)) {rank.put(rootX, tmpSum);// 更新rootY的根节点为rootXparent.put(rootY, rootX);} else {rank.put(rootY, tmpSum);parent.put(rootX, rootY);}// 合并的同时还要维护max值(最长连续序列长)max = Math.max(max, tmpSum);
}
1.4 最终代码
public int longestConsecutive(int[] nums) {if (nums.length == 0) {return 0;}UnionFind unionFind = new UnionFind(nums);for (int num : nums) {// 将当前元素和 +1后的值进行合并unionFind.union(num, num + 1);}return unionFind.max;
}class UnionFind {private Map<Integer, Integer> parent;private Map<Integer, Integer> rank;private int max;public UnionFind(int[] nums) {max = 1;HashMap<Integer, Integer> tmpParent = new HashMap<>();HashMap<Integer, Integer> tmpRank = new HashMap<>();// 初始化操作:每个元素的根节点是它本身。并且以该元素作为根节点时的最长连续序列长度是1for (int num : nums) {tmpParent.put(num, num);tmpRank.put(num, 1);}parent = tmpParent;rank = tmpRank;}public int find(int x) {// 因为我们是以每个元素 + 1 来合并的,因此+1后的元素不一定存在于集合当中。// 这里就要特判if (!parent.containsKey(x)) {return x;}if (parent.get(x) == x) {return x;}parent.put(x, find(parent.get(x)));return parent.get(x);}public void union(int x, int y) {if (!parent.containsKey(y)) {return;}int rootX = find(x);int rootY = find(y);// 是同一个根节点if (rootX == rootY) {return;}int tmpSum = rank.get(rootY) + rank.get(rootX);if (rank.get(rootX) > rank.get(rootY)) {rank.put(rootX, tmpSum);parent.put(rootY, rootX);} else {rank.put(rootY, tmpSum);parent.put(rootX, rootY);}max = Math.max(max, tmpSum);}
}