My really simple Java Solution, using bucket sort


  • -2
    D
    public int firstMissingPositive(int[] nums) {
        if(nums.length==0)  return 1;
            int max=-1;
            for(int i=0;i<nums.length;i++){  
                max=Math.max(max,nums[i]);
            }
            int[] bucket=new int[max+1];
            bucket[0]=1;
            for(int i=0;i<nums.length;i++){
                if(nums[i]>0){
                bucket[nums[i]]=1;
                }
            }
            
         for(int i=0;i<bucket.length;i++){
             if(bucket[i]==0) return i;
         }
            return max+1;
        }

  • 1
    T

    I wonder for this solution, is the space still constant? O(max)?


  • 0
    D

    yes, the space complexity is O(max);


Log in to reply
 

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