LeetCode图解 | 128.最长连续序列
- 2020 年 2 月 24 日
- 筆記
下面开始今天的学习～
今天分享一个LeetCode题，题号是128，标题是最长连续序列，题目标签是并查集和数组。
题目描述
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
解题
看评论和解题都没有详细介绍使用并查集去解这道题的，不过，话说并查集是哪种数据结构组成？
我也不知道并查集是哪一种数据结构，反正它就是一种数据结构。
我个人理解，并查集是两个八竿子打不着关系的团体通过“边”合并在一起，例如，两个节点通过“边”连在一起，两棵树通过“边”形成一颗大树，再例如，图的两个连通分量通过“桥”连在一起形成一个联通分量。所以，我觉得并查集不是“结果”，而是有“过程”的数据结构。
好了，了解并查集，再看题目描述。
输入数组[100, 4, 200, 1, 3, 2]，怎么用并查集表示呢？
我们可以把数组里的六个整数，看成六个独立的团体，而且通过自环连接自己，如下图：
独立的集合
要注意，并查集是子节点是指向父节点的，所以，用数组（直接寻址表）表示并查集的时候，下标是子节点，下标所指的值是父节点；如果数据不是小整数或跨度比较大的时候，用散列表也可以表示并查集，键是子节点，值是父节点。
那怎么进行“并”操作呢？
题目要求得到最长连续序列的长度，那就设定一个集合是连续序列的整数，“并”是将两个集合之间合并在一起，就用“边”连接起来。注意，一个集合可能是一个节点，也可能是已连续的多个节点。
如下图，我用子节点小于父节点连接起来的，当然，你也可以用子节点大于父节点连接起来。
“并”操作
具体的程序代码应该怎样执行，看下面动画就能看清楚什么思路了，大家加油 8-)。
动画：使用并查集
视频大小：2.24M
Code：使用并查集
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循环遍历，忽略相邻两个数相等的情况下，去统计连续序列的最长长度，找到最大值。
喜欢本文的朋友，关注「图解面试算法」，收看有目共赏的算法动画，一起领悟算法的魅力，大家加油 8-）
END
