4/14/2014

Leetcode -- Longest Consecutive Sequence

class Solution {  
 public:  
   int longestConsecutive(vector<int> &num) {  
     unordered_set<int> hash(num.begin(), num.end());  
     unordered_set<int> visited;  
     int maxLen = 0;  
     for(int i =0; i < num.size(); ++i) {  
       if(visited.count(num[i])) {  
         continue;  
       }  
       int length = 0;  
       int smaller = num[i];  
       int larger = num[i]+1;  
       visited.emplace(smaller);  
       while(!(hash.count(smaller) == 0 && hash.count(larger) == 0)) {  
         if(hash.count(smaller) > 0) {  
           visited.emplace(smaller);  
           smaller--;  
           length++;  
         }  
         if(hash.count(larger) > 0) {  
           visited.emplace(larger);  
           larger++;  
           length++;  
         }  
       }  
       maxLen = max(maxLen, length);  
     }  
     return maxLen;  
   }  
 };  

No comments: