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: Update solution. This solution is from Peking2
(http://blog.sina.com.cn/s/blog_b9285de20101iqar.html).
This
solution is much easier to understand.
1 class Solution { 2 public: 3 int longestConsecutive(vector<int> &num) { 4 unordered_set<int> s; 5 int res = 0; 6 for(int i = 0; i < num.size(); i++) { 7 s.insert(num[i]); 8 } 9 for(int i = 0; i < num.size() && !s.empty(); i++) { 10 int lower = num[i], upper = num[i]; 11 if(s.find(num[i]) == s.end()) continue; 12 else s.erase(num[i]); 13 while(s.find(upper+1) != s.end()) { 14 s.erase(++upper); 15 } 16 while(s.find(lower-1) != s.end()) { 17 s.erase(--lower); 18 } 19 res = max(res, upper-lower+1); 20 } 21 return res; 22 } 23 };
Longest Consecutive Sequence,布布扣,bubuko.com
原文：http://www.cnblogs.com/zhengjiankang/p/3659916.html