当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.128.Longest Consecutive Sequence 最长连续序列

LeetCode.128.Longest Consecutive Sequence 最长连续序列

题目描述

128 Longest Consecutive Sequence
https://leetcode-cn.com/problems/longest-consecutive-sequence/

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

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

示例:

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

解题过程

O(n^2)暴力搜索

暴力解法的思想是外层循环遍历数组中每个元素 i,然后内层循环找 i+1 是否在数组中,统计长度并和当前最大连续序列长度对比更新。可以将数组元素放入 set ,就可以实现 O(1) 找 i+1 是否在数组中,但时间复杂度还是 O(n^2)

O(n)哈希剪枝

以 [100, 4, 200, 1, 3, 2] 为例,外层循环以 1 开始时,得到最长连续序列长度为 4,即 [1,2,3,4],之后外层循环遍历到 2,3,4 时其实都是无效的遍历,因为以 2,3,4 开头的序列肯定在以 1 开头的序列中,可以想办法把这些重复的操作去掉。
怎么优化呢?
外层循环我们只需要遍历那些不是某个元素的 +1 后续的元素,即跳过处于某个连续序列中间的元素,就可以把 2,3,4 跳过,还是利用 set,我们只从 i-1 不在 set 中的元素开始遍历查找。

注意两点:
1、数组元素有可能是 int 最小值,此时 i-1 会越界,需要特殊判断一下,当然测试用例中没有这种数据,不考虑也能过。
2、进一步的优化,我们只需要遍历 set 中去重后的元素,而不是原始数组 nums,这个优化对于原始数组中有大量重复数据时有不错的效果。

时间复杂度 O(n),空间复杂度 O(n)

private static class SolutionV202006 {
    public int longestConsecutive(int[] nums) {
        if (null == nums || nums.length < 1) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            set.add(i);
        }
        int maxLength = 0;
        for (int i : nums) {
            // 只遍历没有出现在其他连续序列中的元素, 即 i-1 不存在 set 中的
            if (!set.contains(i - 1)) {
                int length = 1;
                int j = i;
                while (set.contains(j + 1)) {
                    j++;
                    length++;
                }
                maxLength = Math.max(maxLength, length);
            }
        }
        return maxLength;
    }
}

并查集

基本思想是每个连续序列中的元素合并到并查集的一个集合中,代表元是这个集合最小或最大的元素,然后找size最大的集合的size就行。或者也可以找每个元素和他的代表元之间的差值。并查集可以在遍历数组的过程中动态的构造。


GitHub代码

algorithms/leetcode/leetcode/_128_LongestConsecutiveSequence.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_128_LongestConsecutiveSequence.java


上一篇 LeetCode.126.Word Ladder II 单词接龙 II

下一篇 LeetCode.054.Spiral Matrix 螺旋矩阵

阅读
评论
696
阅读预计2分钟
创建日期 2020-06-06
修改日期 2020-06-06
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论