给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
0 1 1 2 输出 3
class Solution {
public:
//法一 排序
int longestConsecutive(vector<int>& nums) {
if(nums.size() == 0){
return 0;
}
sort(nums.begin(),nums.end());
int maxCount=1,tmpCount=1;
for(int i=1;i<nums.size();i++){
if(nums[i] == nums[i-1]+1){
tmpCount++;
maxCount = max(tmpCount,maxCount);
}else if(nums[i] == nums[i-1]){
//0 1 1 2
continue;
}else{
tmpCount = 1;
}
}
return maxCount;
}
};
法二
class Solution {
public:
//o(n)时间复杂度 unordered_map底层是hash表
int longestConsecutive(vector<int>& nums) {
//中心扩展法，向两边查找，利用一个map顺便还可以去重
unordered_map<int,bool> m;
for(int i=0;i<nums.size();i++){
m.insert(pair<int,bool>(nums[i],false));
}
if(m.size() == 0){
return 0;
}
int tmpCount=1,maxCount=1;
map<int,bool>::iterator iter,it;
for(int i=0;i<nums.size();i++){
//关键点
if(m[nums[i]]){
continue;
}
m[nums[i]] = true;
for(int left = nums[i]-1 ;m.find(left)!=m.end();left--){
tmpCount++;
m[left] = true;
}
for(int right = nums[i]+1 ;m.find(right)!=m.end();right++){
tmpCount++;
m[right] = true;
}
maxCount=max(maxCount,tmpCount);
tmpCount = 1;
}
return maxCount;
}
};