LeetCode之Longest Consecutive Sequence

【题目】

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为中心

向右扩张：无

向左扩张：无

【代码】

/*********************************
*   日期：2014-01-17
*   作者：SJF0115
*   题号: Longest Consecutive Sequence
*   来源：http://oj.leetcode.com/problems/longest-consecutive-sequence/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; using namespace tr1; class Solution { public: int longestConsecutive(vector
      
        &num) { int i,j; int CurLength = 0; int MaxLength = 0; int Len = num.size(); // Map中的元素是自动按key升序排序 unordered_map
       
         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
        
          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; }