First Missing Positive

Description

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.

Hint

Train of Thought

Put each number in its right place.

For example:

When we find 5, then swap it with A[4].

At last, the first place where its number is not right, return the place + 1.

Code

public class Solution {
public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for(int i = 0; i < n; i++) {
    //一直循环直到之前的每个正数都在正确的位置上
        while(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
            swap(nums, i, nums[i] - 1);
    }
    for(int i = 0; i < n; i++)
        if(nums[i] != i + 1)
            return i + 1;
    return n + 1;
}

private void swap(int[] nums, int i, int j) {
    nums[i] ^= nums[j];
    nums[j] ^= nums[i];
    nums[i] ^= nums[j];
}

Complexity