首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  程序员

[Leetcode] 128.最长连续序列

  •  
  •   Acceml · 176 天前 · 1154 次点击
    这是一个创建于 176 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

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

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

    示例:

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

    题解

    这道题目最开始大家想的肯定是 sort,然后计数计算最长序列。但是要求时间复杂度为:o(n),就不能用 sort 了。一般在 leetcode 中,对时间复杂度有要求,就用空间来换,对空间复杂度有要求,就用时间来换。

    基于这种思路我们就想要求最长的,就是要记录下有没有相邻的元素,比如遍历到 100 这个元素,我们需要查看[99, 101]这两个元素在不在序列中,这样去更新最大长度。而记录元素有没有这个事我们太熟悉了,用 set 这种数据结构,而 set 这种数据结构是需要 o(n)的空间来换取的,这就是我们刚才说的用空间来换时间。

    class Solution {
        public int longestConsecutive(int[] nums) {
            Set<Integer> numsSet = new HashSet<>();
            for (Integer num : nums) {
                numsSet.add(num);
            }
            int longest = 0;
            for (Integer num : nums) {
                if (numsSet.remove(num)) {
                    // 向当前元素的左边搜索,eg: 当前为 100, 搜索:99,98,97,...
                    int currentLongest = 1;
                    int current = num;
                    while (numsSet.remove(current - 1)) current--;
                    currentLongest += (num - current);
    								// 向当前元素的右边搜索,eg: 当前为 100, 搜索:101,102,103,...
                    current = num;
                    while(numsSet.remove(current + 1)) current++;
                    currentLongest += (current - num);
            				// 搜索完后更新 longest.
                    longest = Math.max(longest, currentLongest);
                }
            }
            return longest;
        }
    }
    

    热门阅读

    Leetcode 名企之路

    5 回复  |  直到 2019-05-20 19:41:58 +08:00
        1
    balaWgc   176 天前
    以后这种文章就别发了行吧
        2
    lovezww2011   176 天前
    你打算每天发一篇吗
        3
    gosansam   176 天前
    我觉得还行呢
        4
    fzy0728   176 天前
    挺棒的
        5
    1069401249   176 天前
    不是 2 层循环吗?时间复杂度不是 0(n)了啊
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2516 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 22ms · UTC 14:25 · PVG 22:25 · LAX 06:25 · JFK 09:25
    ♥ Do have faith in what you're doing.