题目描述:(链接)
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)，于是想到了哈希表，记录每个元素的使用情况，求出最长的长度。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, bool> used;
int longest = 0;
for (auto i : nums) {
used[i] = false;
}
for (auto i : nums) {
if (used[i]) { continue; }
int length = 1;
for (int j = i + 1; used.find(j) != used.end(); ++j) {
used[j] = true;
++length;
}
for (int j = i - 1; used.find(j) != used.end(); --j) {
used[j] = true;
++length;
}
if (length > longest) {
longest = length;
}
}
return longest;
}
};
[LeetCode]Longest Consecutive Sequence
原文：http://www.cnblogs.com/skycore/p/4852715.html