Java solution. no swap, take advantage of negative int.


  • 0
    W

    if every integer which exists in the range, set the position's value to negative.
    then ans is which number is not neg.

    public int firstMissingPositive(int[] nums) {
            for(int i=0;i<nums.length;i++)
                if(nums[i]<=0) nums[i] = Integer.MAX_VALUE;
    
            for(int i=0;i<nums.length;i++){
                int k = Math.abs(nums[i]);
                if(k<=nums.length && nums[k-1]>0)
                    nums[k-1] = -nums[k-1];
            }
            
            for(int i=0;i<nums.length;i++)
                if(nums[i]>0) return i+1;
    
            return nums.length+1;
        }
    

Log in to reply
 

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