JAVA SOLUTION W/ EXPLANATIONS


  • 0
    J

    Basically I throw the negative and overly large numbers to the tail of the array. The tail is not useful for us to search for the missing number. Sort the front part of the array so that it is in ascending order. nums[0]=1,nums[1]=2,nums[2]=3..... like so. Now it becomes easy to find the missing one.

    public int firstMissingPositive(int[] nums){
        int min=1;
        int i=0,tail=nums.length-1;
        while(i<=tail){
            if(nums[i]<=0||nums[i]-1>=nums.length) { swap(nums,i,tail); tail--;} 
            else if(nums[i]==nums[nums[i]-1]) i++;
            else swap(nums,i,nums[i]-1);
        }
        for(int n:nums){
            if(n!=min) return min;
            min++;
        }
        return min;
    }
    void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }

Log in to reply
 

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