LeetCode图解 | 128.最长连续序列

￡神魔★判官ぃ 2023-07-06 14:51 4阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

今天分享一个LeetCode题，题号是128，标题是最长连续序列，题目标签是并查集和数组。

### 题目描述 ###

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
    输出: 4
    
    解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

### 解题 ###

看评论和解题都没有详细介绍使用并查集去解这道题的，不过，话说并查集是哪种数据结构组成？

我也不知道并查集是哪一种数据结构，反正它就是一种数据结构。

我个人理解，并查集是两个八竿子打不着关系的团体通过“边”合并在一起，例如，两个节点通过“边”连在一起，两棵树通过“边”形成一颗大树，再例如，图的两个连通分量通过“桥”连在一起形成一个联通分量。所以，我觉得并查集不是“结果”，而是有“过程”的数据结构。

好了，了解并查集，再看题目描述。

输入数组\[100, 4, 200, 1, 3, 2\]，怎么用并查集表示呢？

我们可以把数组里的六个整数，看成六个独立的团体，而且通过自环连接自己，如下图：

![独立的集合][format_png 2]

独立的集合

要注意，并查集是子节点是指向父节点的，所以，用数组（直接寻址表）表示并查集的时候，下标是子节点，下标所指的值是父节点；如果数据不是小整数或跨度比较大的时候，用散列表也可以表示并查集，键是子节点，值是父节点。

那怎么进行“并”操作呢？

题目要求得到最长连续序列的长度，那就设定一个集合是连续序列的整数，“并”是将两个集合之间合并在一起，就用“边”连接起来。注意，一个集合可能是一个节点，也可能是已连续的多个节点。

如下图，我用子节点小于父节点连接起来的，当然，你也可以用子节点大于父节点连接起来。

![format_png 3][]

“并”操作

具体的程序代码应该怎样执行，看下面动画就能看清楚什么思路了，大家加油 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**

--------------------

![format_png 4][]

● [LeetCode图解|191.位1的个数][LeetCode_191._1]

[● ][Link 1][LeetCode图解|27.移除元素][LeetCode_27.]

● [LeetCode图解|21.合并两个有序链表][LeetCode_21.]

● [LeetCode图解|18.四数之和][LeetCode_18.]

![format_png 5][]

点“在看”你懂得

![format_png 6][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9pY0hvZXJLTzNOakxHa0wzSmljWnh6WlVsTVBXYU9FVXRpYVZ5RHQ1QU9hSUpOa0xhbHRYT1lSaWFHU2J5aWJneFFzVkxSYXo5SnhmTjZLVkJtU05GYkZlNkx3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9ENjdwZWNlaWJlSVJiTkp1c21LYU5tck9QRTdjeDA3bUF3SWVDd1VmenY4T1RCWElOakNOaWJ6aGJJSGhjaWNmMkI5aWFXUUtEZDdkbjZwaWNPaWNZVVpwWUVwZy82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy95OHNTRUtOODJKa3ZqaWJ6VkF3ZFptTDZqdWVRUkN4NGljNnRpYThpYVZCcXNPa0d2TUJVMFhkZWFpYVJkQnlxQlJpY0l4Zmt6S3UzTjIyMlhPTktNbjVSN1RNUS82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy95OHNTRUtOODJKa3ZqaWJ6VkF3ZFptTDZqdWVRUkN4NGljOEswWFluaWFjMDd5M29icFRMZDJGRndHWjZwUnNPSTRlcEN5NVNaY25wWTJkS2E3aWJXVGljWjVnLzY0MA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9wNldsMkxETVFsSEM2cERYeVFSYVdqbFdSNVBJaHVrSVVHVjFuZks2SDlxdEhab3huWHRWZGV6dG9GZXhrYWV2dWRtWjFNYlY5cVdOWlRYaWFvcEx5b1EvNjQw?x-oss-process=image/format,png
[LeetCode_191._1]: https://blog.csdn.net/kexuanxiu1163/article/details/104285220
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e600fcd79e9190507950395a99e2aa74ca79a30111ded2f6076a41da54ba9864068b463ca&idx=2&mid=2247487374&scene=21&sn=6f36c1b402515807731e4a52459f903a#wechat_redirect
[LeetCode_27.]: https://blog.csdn.net/kexuanxiu1163/article/details/104120772
[LeetCode_21.]: https://blog.csdn.net/kexuanxiu1163/article/details/104026516
[LeetCode_18.]: https://blog.csdn.net/kexuanxiu1163/article/details/104151533
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJ1Mlo1T0d1SXpidXdUaWFpYmlhNWxNU3pJSnhabmliTURvdkhpY0lOZ2N3RWtKZXhlVVZkQTZGMVJNMzlGTVJaajE2U3JwOVFtRURpYXZhZmliQS82NDA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jNmdxbWhXaWFmeXI5djFSblJIZGdiRTlWTzljY2pWU0FuOGpxUXBoeUxKbDU5N1JzOUJ6RVViQlIwQUdmSmZ2a3pMOXJ1cWtUbVBBWHIyOXRISWNwRFEvNjQw?x-oss-process=image/format,png