[LeetCode] 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.

方法一

　　先排序，然后找就好了，但是要求是O(n),排序明显是个O(n*logn)的算法.

方法二

只是找连续的嘛,我们可以把所有的数字都存入hash表,然后随意从某个数字开始找他的前面和后面那个是否存在.

然后得到一个最大的长度.当然找过的就可以删掉了...你想,一个连续的序列,你从中间任意位置开始往两边找不都一样么.

所以只要找过就可以删掉了.

 1 class Solution {
 2 public:
 3     set<int> flag;
 4     int findBound(int n , bool asc){
 5         int ans = 0;
 6         set<int>::iterator iter;
 7         while((iter = flag.find(n)) != flag.end()){
 8             flag.erase(iter);
 9             ans ++;
10             if(asc) 
11                 n-- ;
12             else 
13                 n++;
14         }
15         return ans;
16     }
17     int longestConsecutive(vector<int> &num) {
18         // Start typing your C/C++ solution below
19         // DO NOT write int main() function
20              
21         int ans = 0;
22         flag.clear();
23         for(int i = 0 ; i < num.size() ; i++)
24            flag.insert(num[i]);
25         for(int i = 0 ; i < num.size(); i++){
26             ans = max(findBound(num[i],true) + findBound(num[i]+1,false) , ans); 
27         }
28         return ans;
29     }
30 };

下面用hash代替了set，思想一样，看上去没有上面的简洁

 1 class Solution {
 2 public:
 3     int longestConsecutive(vector<int> &num) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         map<int, int> hmap;
 7         hmap.clear();
 8         int n = num.size();
 9         for(int i=0; i<n; i++){
10             hmap.insert(pair<int, int>(num[i], i));
11         }
12         int ans=0, cnt=0;
13         map<int, int>::iterator it;
14         for(int i=0; i<num.size(); i++){
15             int cur = num[i];
16             it = hmap.find(num[i]);
17             cnt = 1;
18             if(it!=hmap.end()){
19                 map<int, int>::iterator iter;
20                 while(1){
21                     iter = hmap.find(++cur);
22                     if(iter==hmap.end())
23                         break;
24                     cnt++;    
25                     hmap.erase(iter);
26                 }
27                 cur=num[i];
28                 while(1){
29                     iter = hmap.find(--cur);
30                     if(iter==hmap.end())
31                         break;
32                     cnt++;    
33                     hmap.erase(iter);
34                 }
35                 if(ans<cnt)
36                     ans = cnt;           
37                 
38             }
39             
40         }
41         return ans;
42     }
43 };