Java Straightforward Solution


  • 6
    D
    1. Use a HashMap<Integer,Boolean>. Use every number in num[] as a key, mark them as not used.

    2. For each number in the hashmap, if the number is not used, select it as the center to grow a sequence on number++ and number--
      directions. Mark used number as used.

    3. After each growth, update the longestSoFar.

    4. Return the longestSoFar.

    5. Since each number is used only once, the time complexity is O(n).

    public class Solution {
        public int longestConsecutive(int[] num) {
            if(num.length<=1)
                return num.length;
            HashMap<Integer,Boolean> numberUsed=new HashMap<Integer,Boolean>();
            for(int i:num)
                numberUsed.put(i,false);
            int longestSoFar=1;
            for(int i:num)
            {
                if(numberUsed.get(i)==false)
                {
                    int localLongest=1;
                    int tmp=i+1;
                    numberUsed.put(i,true);
                    while(numberUsed.containsKey(tmp)&&numberUsed.get(tmp)==false)
                    {
                        localLongest+=1;
                        numberUsed.put(tmp,true);
                        tmp+=1;
                    }
                    tmp=i-1;
                    while(numberUsed.containsKey(tmp)&&numberUsed.get(tmp)==false)
                    {
                        localLongest+=1;
                        numberUsed.put(tmp,true);
                        tmp-=1;
                    }
                    longestSoFar=Math.max(longestSoFar,localLongest);
                }
            }
            return longestSoFar;
        }
    }

  • 0
    M

    nice solution! actually the boolean value is not nessesary. this is my python version using set instead of hashmap:

    class Solution:
    # @param num, a list of integer
    # @return an integer
    def longestConsecutive(self, num):
        unUsedNum, maxlen = set(num), 0
        for numi in num:
            if numi in unUsedNum:
                unUsedNum.remove(numi)
                
                small = numi - 1
                while small in unUsedNum:
                    unUsedNum.remove(small)
                    small -= 1
                
                big = numi + 1
                while big in unUsedNum:
                    unUsedNum.remove(big)
                    big += 1
                
                maxlen = max(maxlen, big - small - 1)
        return maxlen

  • 1
    N

    Actually... This is a O(n^2) solution. Clearly you have some misunderstandings on Big O. And surprisingly, the OJ cannot judge the real big O of this questions.


  • 0
    K

    Hi @nevergone_sc, may I ask why? It seems to me it's O(n)


  • 0
    N

    Sorry! My bad, I didn't think it through! Genius thought!


Log in to reply
 

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