leet-longest consecutive sequence length(最长连续序列长度)

一 概述

Given an unsorted array of itegers,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.

二 分析

如果允许O(nLogn)的复杂度，那么可以先排序，但本题要求O(n).

另外，序列里面的元素是无序的，考虑到使用hash表。

用一个哈希表unordered_map<int,bool> used记录每个元素是否使用，对每个元素，以该元素为中心，往左右扩张，直到不连续为止，记录下最长的长度。

三 代码

[main.cpp]

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution{
public:
int longestConsecutive(const vector<int> &num){
unordered_map<int,bool> used;

for(vector<int>::const_iterator numIterator = num.begin();numIterator != num.end();numIterator++)
used[*numIterator] = false;

int longest = 0;

for(vector<int>::const_iterator numIterator = num.begin();numIterator != num.end();numIterator++){
if(used[*numIterator])
continue;

int length = 1;
used[*numIterator] = true;
int i = *numIterator;
for(int j = i+1;used.find(j) != used.end();++j){
used[j] = true;
++length;
}

for(int j = i-1;used.find(j) != used.end();--j){
used[j] = true;
++length;
}
longest = max(longest,length);
}
return longest;
}
};

int main(int argc, char **argv)
{
Solution *s = new Solution();
int arr[] = {100,4,200,5,9,2,1,3};
vector<int> vectorInt(arr,arr+sizeof(arr)/sizeof(int));
int longestConsecutiveLength = s -> longestConsecutive(vectorInt);
cout<<"longest consecutive sequence length of arr:"<<endl;
for(auto i :vectorInt)
cout<<i<<"\t";
cout<<"\nis "<<longestConsecutiveLength<<endl;
return 0;
}

四 编译及运算结果

编译:

g++ main.cpp  -o longestConsecutiveSequence -std=c++11 -O2

其中:-std=c++11表示启用C++11标准

运算结果:

longest consecutive sequence length of arr: 100 4 200 5 92 1 3 is 5