[Leetcode] #128 Longest Consecutive Sequence

Discription

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.

Solution

如果使用排序，复杂度不满足要求。所以以空间换时间，用unordered_set保存数据，每次选取一个数，看相邻的数是否在set里。这里由于连续的几个数求出的结果是一致的，因此求长度时将遍历到的数从set里擦除，同时循环开始时要判断该数是否在set中。

int longestConsecutive(vector<int>& nums) { //unordered_set<int> values; //for (int num : nums) // values.insert(num); unordered_set<int> values(nums.begin(), nums.end()); int maxlen = 0; for (int x : nums) { if (values.find(x) == values.end()) continue; int len = 1; for (int i = x - 1; values.find(i) != values.end(); i--) { values.erase(i); len++; } for (int i = x + 1; values.find(i) != values.end(); i++) { values.erase(i); len++; } maxlen = max(len, maxlen); } return maxlen; }GitHub-Leetcode: https://github.com/wenwu313/LeetCode