今天分享一个LeetCode题,题号是128,标题是最长连续序列,题目标签是并查集和数组。
给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
看评论和解题都没有详细介绍使用并查集去解这道题的,不过,话说并查集是哪种数据结构组成?
我也不知道并查集是哪一种数据结构,反正它就是一种数据结构。
我个人理解,并查集是两个八竿子打不着关系的团体通过“边”合并在一起,例如,两个节点通过“边”连在一起,两棵树通过“边”形成一颗大树,再例如,图的两个连通分量通过“桥”连在一起形成一个联通分量。所以,我觉得并查集不是“结果”,而是有“过程”的数据结构。
好了,了解并查集,再看题目描述。
输入数组[100, 4, 200, 1, 3, 2],怎么用并查集表示呢?
我们可以把数组里的六个整数,看成六个独立的团体,而且通过自环连接自己,如下图:
独立的集合
要注意,并查集是子节点是指向父节点的,所以,用数组(直接寻址表)表示并查集的时候,下标是子节点,下标所指的值是父节点;如果数据不是小整数或跨度比较大的时候,用散列表也可以表示并查集,键是子节点,值是父节点。
那怎么进行“并”操作呢?
题目要求得到最长连续序列的长度,那就设定一个集合是连续序列的整数,“并”是将两个集合之间合并在一起,就用“边”连接起来。注意,一个集合可能是一个节点,也可能是已连续的多个节点。
如下图,我用子节点小于父节点连接起来的,当然,你也可以用子节点大于父节点连接起来。
“并”操作
具体的程序代码应该怎样执行,看下面动画就能看清楚什么思路了,大家加油 8-)。
import java.util.HashMap;
import java.util.Map;
// 并查集
class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null) return 0;
if (nums.length <= 1) return nums.length;
// 构建并查集
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums)
if (!map.containsKey(num)) {
map.put(num, num);
// 并查集的状态表达
if (map.containsKey(num - 1))
map.put(num - 1, num);
if (map.containsKey(num + 1))
map.put(num, num + 1);
}
// 找到最长
int res = 1;
for (int num : nums) {
if (map.get(num) != num) {
int len = parent(map, num) - num + 1;
res = res > len ? res : len;
}
}
return res;
}
private int parent(Map<Integer, Integer> map, int num) {
if (map.get(num) == num) return num;
return parent(map, map.get(num));
}
}
如果为了提升时间上的效果,可以将未排序的整数数组进行升序,然后进行for循环遍历,忽略相邻两个数相等的情况下,去统计连续序列的最长长度,找到最大值。