# [LeetCode]128.Longest Consecutive Sequence

+关注继续查看

### Longest Consecutive Sequence

Total Accepted: 4743 Total Submissions: 17989

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.

### 【分析】

（1）第一步：以100为中心

（2）第二步：以4为中心

（3）第三步：以200为中心

（4）1，3，2，101........以被扩张，无需以他们为中心进行扩张

### 【代码】

/*********************************
*   日期：2014-01-17
*   作者：SJF0115
*   题号: Longest Consecutive Sequence
*   来源：http://oj.leetcode.com/problems/longest-consecutive-sequence/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <tr1/unordered_map>
using namespace std;
using namespace tr1;

class Solution {
public:
int longestConsecutive(vector<int> &num) {
int i,j;
int CurLength = 0;
int MaxLength = 0;
int Len = num.size();
// Map中的元素是自动按key升序排序
unordered_map<int,bool> used;
//初始化
for(i = 0;i < Len;i++){
used[num[i]] = false;
}
for(i = 0;i < Len;i++){
//如果以扩张，跳过
if(used[num[i]]){
continue;
}
else{
//以num[i]为中心左右扩张，直到不连续为止
used[num[i]] = true;
CurLength = 1;
//向右扩张
for(j = num[i] + 1;used.find(j) != used.end();j++){
CurLength ++;
used[j] = true;
}
//向左扩张
for(j = num[i] - 1;used.find(j) != used.end();j--){
CurLength ++;
used[j] = true;
}
//更新最大长度
if(CurLength > MaxLength){
MaxLength = CurLength;
}
}//if
}//for
return MaxLength;
}
};
int main() {
int result;
Solution solution;
vector<int> vec;
vec.push_back(100);
vec.push_back(4);
vec.push_back(200);
vec.push_back(1);
vec.push_back(3);
vec.push_back(2);
vec.push_back(101);
vec.push_back(99);
vec.push_back(97);
vec.push_back(98);
vec.push_back(102);
result = solution.longestConsecutive(vec);
printf("Result:%d\n",result);
return 0;
}



+关注
sjf0115
Stay Hungry, Stay Foolish---我们必须用谦虚者的自觉，饥饿者的渴望的求职态度，来拥抱我们的未来。