332
[LeetCode]128.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.
【題意】
給出一個沒有排序的整數數組，找出最長的連續元素序列的長度。
例如，
給定[100，4，200，1，3，2]，
最長的連續元素序列是[1，2，3，4]。返回它的長度：4。
你的算法應該運行在O（n）的複雜度。
【分析】
如果允許 O(n log n) 的複雜度，那麼可以先排序，可是本題要求 O(n)。由於序列裏的元素是無序的，又要求 O(n)，首先要想到用哈希表。
用一個哈希表visited[]記錄每個元素是否使用，對每個元素，以該元素為中心，往左右擴張，直到不連續為止，記錄下最長的長度。
在[100，4，200，1，3，2，101，99，97，98，102]的例子中：
（1）第一步：以100為中心
向右擴張：101，102
向左擴張：99，98，97
（2）第二步：以4為中心
向右擴張：無
向左擴張：3，2，1
（3）第三步：以200為中心
向右擴張：無
向左擴張：無
（4）1，3，2，101........以被擴張，無需以他們為中心進行擴張
【代碼】
/*********************************
* 日期：2014-01-17
* 作者：SJF0115
* 題號: Longest Consecutive Sequence
* 來源：https://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;
}
最後更新：2017-04-03 12:54:33