How about this c++ code ?It takes 19ms .


  • 0
    D
    class Solution {
    public:
        int longestConsecutive(vector<int> &num) 
    	{
    		if(num.size() == 0) return 0;
    		if(num.size() == 1) return 1;
    		int len = 1, max = 0;
    		sort(num.begin(),num.end());
    		for(int i=0; i<num.size()-1; ++i)
    		{
    			if(num[i]+1 == num[i+1])
    				++len;
    			else if(num[i] == num[i+1])
    				continue;
    			else
    			{
    				len = 1;
    				if(max >= num.size()-(i+1))// If the current largest length of LCS is greater than the number of remaining ,then break.
    					break;
    			}
    			max = max > len ? max : len;
    		}
    		return max = max > len ? max : len;
        }
    };
    

    The time complexity of sort() is O(nlogn), thus this code doesn't meet the problem's need.

    so ,the right code is here

    class Solution {
    public:
        int longestConsecutive(vector<int> &num) 
    	{
    		if(num.size() <1) return num.size();
    		unordered_map<int,int> a;
    		int len = num.size();
    		int result=0;
    		for(int i=0; i<len; ++i)
    			a.insert(make_pair(num[i],1));
    		for(int i=0; i<len; ++i)
    		{
    			if(a.find(num[i]) == a.end())
    				continue;
    			int findLeft = num[i], findRight = num[i];
    			int max = 1;
    			while(a.find(--findLeft) != a.end())
    			{
    				max += 1;
    				a.erase(findLeft);
    			}
    			while(a.find(++findRight) != a.end())
    			{
    				max += 1;
    				a.erase(findRight);
    			}
    			a.erase(num[i]);
    			result = result > max ? result : max;
    		}
    		return result;
    	}
    };

  • 1
    X

    The time complexity of sort() is O(nlogn), thus this code doesn't meet the problem's need.


  • 0
    D

    this is right , I have fixed it.


  • 0
    O

    You new code is still not O(N) but O(NlogN)


  • 0
    D

    i don't know why ? please explain it . thanks.


  • 0
    B

    the complexity of insert operation in std::map is O(log n)


  • 0
    Y

    why the insertion of map is O(lg n) instead of O(1)?


  • 0
    O

    isn't the code inside the two while loop called more than once?


Log in to reply
 

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