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.

C++:
01 struct Pair
02 {
03     int left;
04     int right;
05     Pair(int a, int b): left(a), right(b){}
06 };
07 
08 class Solution {
09 public:
10     int longestConsecutive(vector<int> &num) {
11         // Start typing your C/C++ solution below
12         // DO NOT write int main() function
13         vector<Pair*> interval;
14         map<int, Pair*> relation;
15         int result=0;
16         int n=num.size();
17         for(int i=0;i<n;i++)
18         {
19             int k=num[i];
20             if(relation.find(k)!=relation.end())
21                 continue;
22             if((relation.find(k1)!=relation.end())
23                &&(relation.find(k+1)!=relation.end()))
24             {
25                 Pair* small=relation[k1];
26                 Pair* big=relation[k+1];
27                 small->right=big->right;
28                 relation[k]=small;
29                 relation[big->right]=small;
30                 continue;
31             }
32             if(relation.find(k1)!=relation.end())
33             {
34                 relation[k1]->right++;
35                 relation[k]=relation[k1];
36                 continue;
37             }
38             if(relation.find(k+1)!=relation.end())
39             {
40                 relation[k+1]->left;
41                 relation[k]=relation[k+1];
42                 continue;
43             }
44             Pair* item=new Pair(k,k);
45             relation[k]=item;
46             interval.push_back(item);
47         }
48         for(int i=0;i<interval.size();i++)
49         {
50             if(interval[i]->rightinterval[i]->left+1>result)
51                 result=interval[i]->rightinterval[i]->left+1;
52         }
53         return result;
54     }
55 };
Advertisements
This entry was posted in Array and linked list, Hashtable and Map. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s