做网站知道访客ip,做搜狗手机网站快速,济南企业营销型网站建设价格,网站定制公司哪家好想要精通算法和SQL的成长之路 - 最长连续序列 前言一. 最长连续序列1.1 并查集数据结构创建1.2 find 查找1.3 union 合并操作1.4 最终代码 前言 想要精通算法和SQL的成长之路 - 系列导航 并查集的运用 一. 最长连续序列
原题链接 这个题目#xff0c;如何使用并查集是一个小难… 想要精通算法和SQL的成长之路 - 最长连续序列 前言一. 最长连续序列1.1 并查集数据结构创建1.2 find 查找1.3 union 合并操作1.4 最终代码 前言 想要精通算法和SQL的成长之路 - 系列导航 并查集的运用 一. 最长连续序列
原题链接 这个题目如何使用并查集是一个小难点我们可以这么想
对于数组中的每一个元素在初始化的时候根节点是它本身。以它为根节点的最长连续序列是1。在经历过一系列的合并操作之后以示例1来说元素4的根节点就是元素1。那么我们合并操作合并的对象是谁注意题目要求的是连续序列。那么针对每个元素num我进行union(num,num1)即可。由于题目要求的是最长的连续序列因此我们可以在并查集中维护一个max最大值。在合并操作的时候更新它。由于数组内元素的跳跃性我们可以用一个HashMap替代并查集的int[]数组。
1.1 并查集数据结构创建
class UnionFind {private MapInteger, Integer parent;private MapInteger, Integer rank;private int max;public UnionFind(int[] nums) {max 1;HashMapInteger, Integer tmpParent new HashMap();HashMapInteger, 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,num1)操作以nums [100,4,200,1,3,2]为例那么1001 101101这个元素是否在集合当中呢
我们看下常规的函数
public int find(int x) {while (x ! parent[x]) {x parent[x];}return x;
}而我们在本题当中使用HashMap作为替换存储同时我们还需要考虑到对象不存在的情况代码如下
public int find(int x) {// 因为我们是以每个元素 1 来合并的因此1后的元素不一定存在于集合当中。// 这里就要特判否则就会导致NPEnull和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 MapInteger, Integer parent;private MapInteger, Integer rank;private int max;public UnionFind(int[] nums) {max 1;HashMapInteger, Integer tmpParent new HashMap();HashMapInteger, 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);}
}
