刷题128. Longest Consecutive Sequence

一、题目说明

题目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.
上一篇:算法竞赛入门经典 习题3-1


下一篇:leetcode 829. Consecutive Numbers Sum