[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.

hash table查找的时间复杂度O(1)，可以是时间复杂度降为O(n)。

 1 class Solution {
 2 public:
 3     int longestConsecutive(vector<int>& nums) {
 4         if(nums.size()<1) return 0;
 5         int result=0;
 6         unordered_map<int,int> showed;
 7         for(int i=0;i<nums.size();i++)
 8         {
 9             showed[nums[i]]=1;
10         }
11         for(int i=0;i<nums.size();i++)
12         {
13             int number = nums[i];
14             int times=0;
15             if(showed.find(number)!=showed.end())
16             {
17                 showed.erase(number);
18                 times=1;
19                 for(int j=number-1;;j--)
20                 {
21                     if(showed.find(j)!=showed.end())
22                     {
23                         showed.erase(j);
24                         times++;
25                     }
26                     else
27                     {
28                         break;
29                     }
30                 }
31                 for(int j=number+1;;j++)
32                 {
33                     if(showed.find(j)!=showed.end())
34                     {
35                         showed.erase(j);
36                         times++;
37                     }
38                     else
39                     {
40                         break;
41                     }
42                 }
43             }
44             result = max(result,times);
45         }
46         return result;
47     }
48 };