My easy and simple 10 lines solution using set(add elements to set and scan it once to get longest seq)


  • -3
    G
    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            set<int> myset;
            for(int i=0;i<nums.size();i++) myset.insert(nums[i]);
            set<int>::iterator it=myset.begin();
            int ans=0,count,prev;
            while(it!=myset.end()){
                count=0,prev = *it-1;
                while(it!=myset.end() && *it==prev+1)
                    prev=*it,it++,count++;
                ans = max(count,ans);
            }
            return ans;
        }
    };

  • 0
    S

    I don't think it's a O(n) algorithm, the construction of set takes O(nlog(n))


  • 0
    G

    i never said it's an O(n) solution,obviously it is O(nlogn)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.