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)时间复杂度,所以不能排序。将数据放入哈希表,这样查找时间复杂度是O(1),遍历到某个数据,可以向前和向后找它的连续序列。再用一个哈希表存储已访问过的元素,这样保证每个元素至多被处理一次。
哈希表在C++中用unordered_set实现。set的实现是红黑树,插入查找删除的时间复杂度是O(logn)不能使用。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> visited;
unordered_set<int> exist;
int ret = ;
int count;
int target; for(int i = ; i < nums.size(); i++){
exist.insert(nums[i]);
} for(int i = ; i < nums.size(); i++){
if(visited.find(nums[i])!=visited.end()) continue; visited.insert(nums[i]);
count = ;
target = nums[i];
while(exist.find(--target)!=visited.end()){
visited.insert(target);
count++;
}
target = nums[i];
while(exist.find(++target)!=visited.end()){
visited.insert(target);
count++;
}
if(count > ret) ret = count;
}
return ret;
}
};