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

[Leetcode] 128.最长连续序列

  •  
  •   Acceml ·
    Acceml · 2019-05-20 08:51:21 +08:00 · 1907 次点击
    这是一个创建于 1774 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

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

    要求算法的时间复杂度为 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
    balaWgc
        1
    balaWgc  
       2019-05-20 08:55:18 +08:00
    以后这种文章就别发了行吧
    lovezww2011
        2
    lovezww2011  
       2019-05-20 09:17:14 +08:00
    你打算每天发一篇吗
    gosansam
        3
    gosansam  
       2019-05-20 10:04:46 +08:00
    我觉得还行呢
    fzy0728
        4
    fzy0728  
       2019-05-20 13:04:07 +08:00
    挺棒的
    1069401249
        5
    1069401249  
       2019-05-20 19:41:58 +08:00
    不是 2 层循环吗?时间复杂度不是 0(n)了啊
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1034 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 19:20 · PVG 03:20 · LAX 12:20 · JFK 15:20
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.