LeetCode: 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.
地址：https://oj.leetcode.com/problems/longest-consecutive-sequence/
算法：其实这道题最重要的是利用map中可以按关键字有序遍历的特性。首先，将数组中所有元素存储在map里，这样相当与可以在线性时间内对数组排序，其实就是用空间换时间的方法。代码：
1 class Solution {
2 public:
3 int longestConsecutive(vector<int> &num) {
4 if(num.empty()) return 0;
5 map<int, int> hash_table;
6 for(int i = 0; i < num.size(); ++i){
7 hash_table[num[i]] = num[i];
8 }
9 map<int,int>::iterator it = hash_table.begin();
10 int max_length = 1;
11 int pre_ele = it->first;
12 int length = 1;
13 ++it;
14 for(; it != hash_table.end(); ++it){
15 if(it->first == pre_ele + 1){
16 ++length;
17 }else{
18 if(length > max_length){
19 max_length = length;
20 }
21 length = 1;
22 }
23 pre_ele = it->first;
24 }
25 if(length > max_length)
26 max_length = length;
27 return max_length;
28 }
29 };