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 class Solution {
02 public:
03     int longestConsecutive(vector<int> &num) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06 
07         int n=num.size();
08         if(n==0)
09             return 0;
10         int result=1;
11         map<int, int> A;
12         for(int i=0;i<n;i++)
13         {
14             if(A.find(num[i])!=A.end())
15                 continue;
16             if((A.find(num[i]1)==A.end())
17                &&(A.find(num[i]+1)==A.end()))
18             {
19                 A[num[i]]=1;
20             }
21             else if(A.find(num[i]1)==A.end())
22             {
23                 A[num[i]]=A[num[i]+1]+1;
24                 int large=num[i]+A[num[i]+1];
25                 A[large]=A[num[i]];
26                 if(A[num[i]]>result)
27                     result=A[num[i]];
28             }
29             else if(A.find(num[i]+1)==A.end())
30             {
31                 A[num[i]]=A[num[i]1]+1;
32                 int small=num[i]A[num[i]1];
33                 A[small]=A[num[i]];
34                 if(A[num[i]]>result)
35                     result=A[num[i]];
36             }
37             else
38             {
39                 int large=num[i]+A[num[i]+1];
40                 int small=num[i]A[num[i]1];
41                 A[num[i]]=A[large]=A[small]=largesmall+1;
42                 if(largesmall+1>result)
43                     result=largesmall+1;
44             }
45         }
46         return result;
47     }
48 };
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