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.

Analysis

• scan A[i],把正的并且小于len的数放在A[A[i]-1]
• 比如1放在A[0],2放在A[1],3放在A[2] etc...
• 最后从头扫一遍看哪个index的数不对就是应该返回的数
• 如果都对就返回最后一个数+1

Example 1: (全是正数，有值大于len的数)
3,2,5,1,7
5,2,3,1,7
7,2,3,1,5
1,2,3,7,5
return 4

Example 2:(有0)
1,2,0
1,2,0
return 3

Example 3:（有负数）
3,4,-1,1
-1,4,3,1
-1,1,3,4
1,-1,3,4
return 2

Example 4:（全是正数，且全在范围内，返回最后一个数+1）
2,3,1
3,2,1
1,2,3
return 4

Code

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

Reference

• Yu
• Leetcode