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.
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int n = nums.size(), maxi = , cnt, i, k;
if(n <= )
return ;
unordered_set<int> numsSet;
for(i = ; i < n; i++)
{
numsSet.insert(nums[i]);
}
for(i = ; i < n; i++)
{
cnt = ;
numsSet.erase(nums[i]);
for(k = nums[i]+; numsSet.find(k) != numsSet.end(); k++)
{
cnt++;
numsSet.erase(k);
}
for(k = nums[i]-; numsSet.find(k) != numsSet.end(); k--)
{
cnt++;
numsSet.erase(k);
}
if(cnt > maxi)
maxi = cnt;
}
return maxi;
}
};
先遍历数组，把所有元素放到一个set中。
然后再遍历数组，对每个元素，在set中找比它大的连续数字和比它小的连续数字，若找到则计数器加一，同时从set中删除这个数字。