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

  • 0

    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.