题目大意:
给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
解题思路:
我们每次枚举数字的第一个,然后往后数有多少个。可以证明每个数字只会被枚举一次。注意,中间用hash。
class Solution {
public:
unordered_set<int> ms;
int longestConsecutive(vector<int>& nums) {
int ans = 0;
for(auto it:nums)ms.insert(it);
for(auto it:ms){
if(!ms.count(it-1)){
int no = it;
int len = 1;
while(ms.count(no))no++,len++;
ans = max(ans,len-1);
}
}
return ans;
}
};
第二种方法是排序+递推
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.size() == 0)return 0;
int ans = 1;
sort(nums.begin(),nums.end());
vector<int> dp(nums.size(),0);
dp[0] = 1;
int n = nums.size();
for(int i =1;i<n;i++){
if(nums[i] == nums[i-1]+1)dp[i] = dp[i-1]+1;
else if(nums[i] == nums[i-1])dp[i] = dp[i-1];
else dp[i] = 1;
ans = max(ans,dp[i]);
}
return ans;
}
};
标签:hash,nums,int,ms,ans,128,leetcode,dp,size From: https://blog.51cto.com/u_15910522/5931553