41. First Missing Positive

Problem:

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

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Analysis:
不是很喜欢这道题，太数学了，面试遇到100%挂。
Store nums[nums[i] - 1] to nums[i], if not swap them. Then loop through nums, if nums[i] != i + 1, i + 1 is the first missing positiv integer.

index	0	1	2	3
nums	3	4	-1	1
Swap 0,2	-1	4	3	1
Swap 2,3	-1	1	3	4
Swap 0, 1	1	-1	3	4

After first loop, we can find out that index 1 stores the invalid number. it needs to be 2.

Solution:

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[nums[i] - 1] != nums[i]) {
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1)
                return i + 1;
        }
        return n + 1;
    }
}