41. First Missing Positive

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.

Solution:

We use the array itself as a hash table.

The idea is to swap number i + 1 to index i.

If nums[i] <= 0 || nums[i] >= n, it cannot be the first positive. We skip it.

If nums[i] == i + 1, this number is in its correct position. We skip it.

If nums[i] != i + 1, and nums[i] > 0 && nums[i] < n, we swap it to its correct position.

Be care for in this case, if nums[i] == nums[nums[i] - 1], there is an infinite loop. We simply skip it.



Code:

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