A java algorithm,i don't think this is O(n) complexity,but it's accepted.


  • 2
    P
    public int longestConsecutive(int[] num) {
            HashSet<Integer> hs = new HashSet<Integer>();
            for(int i:num)
            	hs.add(i);
    
            int maxlen=0;
            
            for(int i:num)
            {
            	if(!hs.contains(i))
            		continue;
            	
            	int len =1;     
            	hs.remove(i);
            	
            	int smaller = i-1;
            	while(hs.contains(smaller))
            	{
            		len++;
                	hs.remove(smaller);
            		smaller--;
            	}
            	
            	int bigger = i+1;
            	while(hs.contains(bigger))
            	{
            		len++;
                	hs.remove(bigger);
                	bigger++;
            	}
            	
            	if(len>maxlen)
            		maxlen = len;
            }
    
    		return maxlen;
        }

  • 0
    S
    This post is deleted!

  • 0
    S

    i think this algorithm IS of O(n) complexity! this algorithm consists of: (A). N times contains() of each num[] element, and (B). (Li+2) times contains() for each consecutive sequence(Li=len), to sum up, that's N+(number of sequences)*2 < 3N sorry for poor english, writing from Didu


Log in to reply
 

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