longest consecutive sequence

longest consecutive sequence

Seems hard

This problem looks hard, and I did not find any pretty solutions. The book 《creaking the coding interview》has a famous saying:"heashtable may help you.". Put all element in a map, then for each in the vector figure out the left an d right length. When search left and right element, we can erase the element which already searched by us, and this limited the time complexity to O(n).

 1 class Solution {
 2 public:
 3     int longestConsecutive(vector<int> &num) {
 4         int n = num.size();
 5         if ( 0 == n ) {
 6             return 0;
 7         }
 8         map< int, int > numMap;
 9         for ( int i = 0; i < n; i++ ) {
10             numMap[num[i]] = 1;
11         }
12         int result = 0;
13         for ( int i = 0; i < n; i++ ) {
14             int t = num[i];
15             int now = 0;
16             if ( numMap.find(t) != numMap.end() ) {
17                 numMap.erase(t);
18                 now = 1;
19                 int left = t-1;
20                 while( numMap.find(left) != numMap.end() ) {
21                     numMap.erase(left);
22                     left--;
23                     now++;
24                 }
25                 int right = t+1;
26                 while ( numMap.find(right) != numMap.end() ) {
27                     numMap.erase(right);
28                     right++;
29                     now++;
30                 }
31             }
32             result = max(result,now);
33         }
34         return result;
35     }
36 };

Loading Disqus comments...
Table of Contents