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.

 

 题意在线性的时间内找到集合中元素组成的最长的连续序列。

 

规定只能线性的复杂度，显然不能排序了，就想到用哈希去标记处理。

 

先遍历一边把所有的元素存起来，然后重头遍历，每遇到一个没处理过的元素，

 

用两个指针分别向两个方向寻找连续的元素，记录长度，并把元素标记成处理过，防止重复处理。

 

开始用静态数组标记，发现数据范围爆了，改成map去存就过了。

 

严格上应该写成哈希表的形式，map存储的复杂度大于O（n），但时间没卡那么紧，意思明白就行懒得改了。

 
class Solution {  
public:  
    int longestConsecutive(vector<int> &num) {  
        map<int,bool>m;  
        int i,j,k,len=num.size(),maxx=0;  
        for(i=0;i<len;++i)m[num[i]]=true;  
        for(i=0;i<len;++i)  
        {  
            if(m[num[i]]==true)  
            {  
                m[num[i]]=0;  
                int n=1;  
                int left=num[i]-1,right=num[i]+1;  
                while(m[left]==true)  
                {  
                    m[left--]=0;  
                    n++;                      
                }  
                while(m[right]==true)  
                {  
                    m[right++]=0;  
                    n++;  
                }  
                maxx=max(maxx,n);  
            }  
        }  
        return maxx;          
    }  

 

补充：软件开发 , C++ ,