5ms simple solution but O(nlogn)


  • 1

    The steps are:

    • sort the array
    • check the values
    • return the result
    public int longestConsecutive(int[] nums) {
            // sort the array
            Arrays.sort(nums);
            // final result
            int res = 1;
            // partial result
            int tmp = 1;
    
            for(int i = 1; i < nums.length; i++){
                // ignore the same num
                if(nums[i] ==  nums[i-1]){
                    continue;
                }
                // count the consecutive num
                else if(nums[i-1] + 1 == nums[i]){
                    tmp++;
                }
                // reset the tmp var and check the max
                else {
                    if(tmp >= res)
                        res = tmp;
                    tmp = 1;
                }
            }
            // correct last iteration
            if(tmp > res){
                res = tmp;
            }
    
            return res;
        }
    

  • 0
    D

    your solution maybe O(n), because you go through the whole array, that will costs O(n).


  • 0

    @dader the problem is Arrays.sort(), it has O(nlogn)


  • 1

    Ironically, it is faster that most of O(n) solutions...


  • 0
    C

    Is this an accepted solution. Thought it requires O(n) complexity... I got TLE when using this approach...


Log in to reply
 

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