首页 > 代码库 > [LeetCode] Longest Consecutive Sequence

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

      First of all,if there is no time complexity,we could sort the array,and then scan the array.Unfortunately,the time complexity is O(n*log n).It‘s been many times,when I am asked to solve a problem in O(n) which can be solved in O(n*log n) by using classical quicksort I would use a alternative method--hash table to do it.Here is the code.

 1 class Solution { 2 public: 3     int longestConsecutive(vector<int> &num) { 4         unordered_map<int,bool> hashmap; 5         int maxlength = 0; 6         int curlength = 0; 7          8         for(vector<int>::iterator iter = num.begin(); 9             iter!=num.end();++iter){10             hashmap.insert(pair<int,bool>(*iter,true));11         }12         13         for(vector<int>::iterator iter = num.begin();14             iter!=num.end();++iter){15             int num = *iter;16             curlength = 0;17             while(hashmap.find(num) != hashmap.end()){18                 ++curlength;19                 hashmap.erase(num);20                 ++num;21             }22             23             num = *iter-1;24             while(hashmap.find(num) != hashmap.end()){25                 ++curlength;26                 hashmap.erase(num);27                 --num;28             }29             30             maxlength = maxlength<curlength?curlength:maxlength;31         }32         return maxlength;33     }34 };            

 

[LeetCode] Longest Consecutive Sequence