一、题目说明
题目128. Longest Consecutive Sequence,给定一列无序的整数,计算最大连续的整数的个数。复杂度要求是O(n),难度是Hard!
二、我的解答
这个题目解答方法包括,brute force、sort、hash。但brute force和sort的复杂度不符合要求,此处用hash。
我总共写了2个版本,第1个版本 Time Limit Exceeded,代码如下:
class Solution{
public:
int longestConsecutive(vector<int>& nums){
if(nums.size()<1) return 0;
if(nums.size()==1) return 1;
unordered_map<int,int> dp;
for(int i=0;i<nums.size();i++){
dp[nums[i]] = 1;
}
int max = 1;
for (unordered_map<int, int>::iterator x = dp.begin(); x!= dp.end(); x++){
int n = x->first -1;
while(dp.count(n)>0){
dp[n]++;
if(max<dp[n]) max = dp[n];
n--;
}
n = x->first +1;
while(dp.count(n)>0){
dp[n]++;
if(max<dp[n]) max = dp[n];
n++;
}
}
return max;
}
};
三、优化措施
后来结合其他大神的做法,优化如下:
class Solution{
public:
int longestConsecutive(vector<int>& nums){
if(nums.size()<1) return 0;
if(nums.size()==1) return 1;
unordered_map<int,bool> dp;
for(int i=0;i<nums.size();i++){
dp[nums[i]] = false;
}
int maxNum = 0;
for (int i=0;i<nums.size();i++){
if(dp[nums[i]]) continue;
int len = 1;
dp[nums[i]] = true;
for(int j=nums[i]+1;dp.find(j)!=dp.end();j++){
dp[j] = true;
len++;
}
for(int j=nums[i]-1;dp.find(j)!=dp.end();j--){
dp[j] = true;
len++;
}
maxNum = max(maxNum,len);
}
return maxNum;
}
};
Runtime: 8 ms, faster than 96.28% of C++ online submissions for Longest Consecutive Sequence.
Memory Usage: 10.2 MB, less than 57.69% of C++ online submissions for Longest Consecutive Sequence.