[Leetcode] Longest Consecutive Sequence 最长连续数列

lei___ 发布于2019-08-14 12:38 / 1522人阅读

摘要：集合法复杂度时间空间思路将所有数都加入集合中，然后再遍历这些数，因为我们能的判断某个数是否在集合中，所以我们可以一个个向上或者向下检查。时间复杂度仍是，因为我们不会检查不存在于数组的数，而存在于数组的数也只会检查一次。

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

排序法 复杂度

时间 O(NlogN) 空间 O(1)

思路

将数组排序后，从前向后遍历，找到最长的连续部分，该方法随不符合题意，但是不用空间。

集合法 复杂度

时间 O(N) 空间 O(N)

思路

将所有数都加入集合中，然后再遍历这些数，因为我们能O(1)的判断某个数是否在集合中，所以我们可以一个个向上或者向下检查。为了避免之后重复检查，我们每查到一个数，都要将其从集合中移除。这样每遇到一个数，都检查它的上下边界，就能找出最长的连续数列。时间复杂度仍是O(N)，因为我们不会检查不存在于数组的数，而存在于数组的数也只会检查一次。

代码

public class Solution {
    public int longestConsecutive(int[] nums) {
        int maxlen = 0;
        Set set = new HashSet();
        // 先将所有数字加入数组中
        for(int n : nums){
            set.add(n);
        }
        // 对于每个数我们都在集合中一一检查它的上下边界
        for(int n : nums){
            // 暂存n，供检查下边界时使用
            int curr = n, len = 0;
            // 一个一个检查上边界
            while(set.contains(curr)){
                curr++;
                len++;
                set.remove(curr);
            }
            // 一个一个检查下边界
            curr = n - 1;
            while(set.contains(curr)){
                curr--;
                len++;
                set.remove(curr);
            }
            maxlen = Math.max(len, maxlen);
        }
        return maxlen;
    }
}

海外云主机服务器托管 Longest Sequence Consecutive LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64610.html

[Leetcode] Binary Tree Longest Consecutive Sequenc

摘要：递归法复杂度时间空间思路因为要找最长的连续路径，我们在遍历树的时候需要两个信息，一是目前连起来的路径有多长，二是目前路径的上一个节点的值。代码判断当前是否连续返回当前长度，左子树长度，和右子树长度中较大的那个 Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...

xi4oh4o 2019-08-14 16:16 评论0 收藏0
128. Longest Consecutive Sequence-从数组中寻找最长的连续数字

摘要：描述例子要求分析从未排序的数组中寻找最长的连续的数字，必然要循环一遍所有的数字，因为连续，所以以出来的数字为基准，向左右扩散，直到没有连续的，利用了和的特性。描述： Given an unsorted array of integers, find the length of the longest consecutive elements sequence. 例子： Given ...

Pandaaa 2019-07-30 16:09 评论0 收藏0
[LintCode/LeetCode] Longest Consecutive Sequence

摘要：先排序，然后用数组记录每一位上连续序列的长度，每次循环更新最大值存为。 Problem Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Clarification Your algorithm should run in O(n) com...

buildupchao 2019-08-14 16:25 评论0 收藏0
[LeetCode] 549. Binary Tree Longest Consecutive Se

Problem Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree. Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] ...

bingchen 2019-08-19 11:11 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0