[LeetCode]128.Longest Consecutive Sequence

本文主要是介绍[LeetCode]128.Longest Consecutive Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目】

【题意】

给出一个没有排序的整数数组，找出最长的连续元素序列的长度。 
例如， 
给定[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
*   来源：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}//forreturn 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;
}

这篇关于[LeetCode]128.Longest Consecutive Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---