LeetCode——Longest Consecutive Sequence

Question

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.

Subscribe to see which companies asked this question.

Hide Tags

Solution

这道题对时间复杂度要求比较高，排个序也得O(nlgn)，所以想要得到O(n)，那必须得用空间换时间，用上哈希表。 用哈希表的时候不要用set，因为set插入一个元素的时间复杂度是O(n)，应该选择用unorder_set。

然后遍历每个数字的时候，考虑去集合中查找有没有比这个数大1或者小1的，有的话就继续查找。

我们会发现，遍历4的时候，得到的集合是1， 2， 3， 4， 遍历1的时候也是得到1， 2， 3， 4， 这就重复了呀，所以再遍历4的时候，就应该把找到的元素从集合中去掉，以免重复计算，加大了时间复杂度，具体实现如下：

class Solution {

public:

    int longestConsecutive(vector<int> &num) {

		unordered_set<int> table(num.begin(), num.end());

        int res = 0;

        for (int i : num) {

            if (table.find(i) == table.end()) continue;

            table.erase(i);

            int pre = i - 1;

            int next = i + 1;

            while (table.find(pre) != table.end()) table.erase(pre--);

            while (table.find(next) != table.end()) table.erase(next++);

            res = max(res, next - pre - 1);

        }

        return res;

    }

};