Question

Formatted question description: https://leetcode.ca/all/41.html

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

@tag-array

Algorithm

Put 1 in the first position nums[0] of the array and 2 in the second position nums[1], that is, you need to put nums[i] on nums[nums[i]-1] to traverse the entire array,

  • If nums[i] != i + 1, and nums[i] is an integer and is not greater than n, and nums[i] is not equal to nums[nums[i]-1], swap the two positions,
  • if not satisfied above conditions are skipped directly, and the array is traversed again. If the number at the corresponding position is incorrect, the correct number will be returned.

Note

The key is to deal with the collision. If there are repeated numbers 1, 1, or 2, 2. If the collision means that there is the correct number at the correct position, ++ will go to the next one.

Code

Java

import java.util.Arrays;

public class First_Missing_Positive {

	public class Solution {
	    public int firstMissingPositive(int[] nums) {
	        if (nums == null || nums.length == 0) {
	            return 1;
	        }

	        // two pointers, in plcace sort
	        int i = 0;
	        while (i < nums.length) {

                while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                    // put nums[i] to index nums[i]-1
                    int digit = nums[i];
                    int swapIndex = digit - 1;

                    int tmp = nums[swapIndex];
                    nums[swapIndex] = digit;
                    nums[i] = tmp;
                }

                i++;
            }

            // another scan for the missing one
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] != j + 1) {
                    return j + 1;
                }
            }

            // @note: case for [1,2,3,4,5]
            return nums.length + 1;
        }
    }

All Problems

All Solutions