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.
数据元素无序但要求时间复杂度O(n)应联想到hash.
stl中unordered_map(c++ 11) 和 hash_map 速度比map(红黑树实现)快。新的标准推荐用unordered_map代替hash_map。
1 class Solution { 2 public: 3 int longestConsecutive(vector<int> &num) { 4 unordered_map<int, bool> table; 5 for (auto i : num) { 6 table[i] = false; 7 } 8 int ret = 0; 9 for (auto i : num) { 10 if (table[i]) continue; 11 table[i] = true; 12 int len = 1; 13 for (int j = i + 1; table.find(j) != table.end(); ++j) { 14 ++len; 15 table[j] = true; 16 } 17 for (int j = i - 1; table.find(j) != table.end(); --j) { 18 ++len; 19 table[j] = true; 20 } 21 if (len > ret) ret = len; 22 } 23 return ret; 24 } 25 };
【Leetcode】Longest Consecutive Sequence,布布扣,bubuko.com
【Leetcode】Longest Consecutive Sequence
原文：http://www.cnblogs.com/dengeven/p/3603946.html
