128 - Longest Consecutive Sequence

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.

Hide Tags

Array

既然是 O(n)，又不知道数组的取值范围，那只能是哈希了，
把所有值过一遍，然后再从小到大检查连续性，同步更新最大的连续个数即可。
刚开始用map做了一次，28 ms，改用 set 之后，24 ms。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        set<int> buf;
        for(auto n : nums)
            buf.insert(n);
       
        int rst=0, consecutive=0, last = 0;
        for(auto b : buf)
        {
            b==last+1 ? consecutive++ : consecutive=1;
            rst  = max(rst, consecutive);
            last=b;
        }
        return rst;
    }
};
24 ms.