Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Clarification
Your algorithm should run in O(n) complexity.
Example
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is[1, 2, 3, 4]. Return its length: 4.
LeetCode上的原题，请参见我之前的博客Longest Consecutive Sequence。
解法一：
class Solution { public: /** * @param nums: A list of integers * @return an integer */ int longestConsecutive(vector<int> &num) { int res = 0; unordered_set<int> s(num.begin(), num.end()); for (int d : num) { if (!s.count(d)) continue; s.erase(d); int pre = d - 1, next = d + 1; while (s.count(pre)) s.erase(pre--); while (s.count(next)) s.erase(next++); res = max(res, next - pre - 1); } return res; } };
解法二：
class Solution { public: /** * @param nums: A list of integers * @return an integer */ int longestConsecutive(vector<int> &num) { int res = 0; unordered_map<int, int> m; for (int d : num) { if (m.count(d)) continue; int left = m.count(d - 1) ? m[d - 1] : 0; int right = m.count(d + 1) ? m[d + 1] : 0; int sum = left + right + 1; m[d] = sum; res = max(res, sum); m[d - left] = sum; m[d + right] = sum; } return res; } };
本文转自博客园Grandyang的博客，原文链接：求最长连续序列[LintCode] Longest Consecutive Sequence ，如需转载请自行联系原博主。
