LeetCode 128 Longest Consecutive Sequence

Tag: 数组问题 LeetCode Posted on 2022-02-18 23:18:57 Edited on 2022-02-19 10:25:16 Views: 271

概述

https://leetcode.com/problems/longest-consecutive-sequence/

要求 O(n) 时间复杂度。

直接法

假设最长序列为从 i 到 j,不排序的话,我们要怎么记录从 i 到 j 是连续的呢?

目前一个想法是,从头遍历数组,维护一组连续列表,每遇到一个值,就判断是否之前存在可以加上去的列表。

那要怎么 O(n) 时间复杂度下完成列表的更新呢?其只能是 O(1)。

我们为维护两个哈希表中的项,一个 key 为每个列表的起始值,一个 key 为列表的结束值,value 就存列表的长度。

遍历一遍后,我们需要再遍历一遍列表,看看有没有能够合并的。

注意防范重复值,再加个 map 就好了。

62 / 70 test cases passed:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> start;
        unordered_map<int, int> end;
        unordered_map<int, bool> visited;
        int ans = 0;
        for (auto n : nums) {
            if (visited[n]) continue;
            visited[n] = true;
            if (start[n+1] != 0 && end[n-1] != 0) {
                int newNum = start[n+1] + end[n-1] + 1;
                ans = max(newNum, ans);
                start[n-end[n-1]] = ans;
                end[n+start[n+1]] = ans;
                start.erase(n+1);
                end.erase(n-1);
            } else if (start[n+1] != 0) {
                start[n] = start[n+1] + 1;
                end[n+start[n+1]] ++;
                start.erase(n+1);
                ans = max(ans, start[n]);
            } else if (end[n-1] != 0) {
                end[n] = end[n-1] + 1;
                start[n-end[n-1]] ++;
                end.erase(n-1);
                ans = max(ans, end[n]);
            } else {
                start[n] = 1;
                end[n] = 1;
                ans = max(ans, 1);
            }
        }

        return ans;
    }
};

没找到 bug 在哪,不浪费时间了。

只从 streak 的开始处开始检查

https://leetcode.com/problems/longest-consecutive-sequence/discuss/41057/Simple-O(n)-with-Explanation-Just-walk-each-streak

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int ans = 0;
        for (auto n : nums) {
            if (s.count(n-1) == 0) {  // only start from the start of a streak
                int y = n;
                while (s.count(y)) y ++;
                ans = max(ans, y - n);
            }
        }
        return ans;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/