First Missing Positive

Problem

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.

---

Idea

首先确定最后的missing positive一定是 在[1...n-1]之间

用A[i]记录i+1， 因为0不算正数

对于每一个A[i]， 如果不等于i+1,则和A[A[i]-1]换位置。

最后遍历一遍，找不是i+1的。

---

Solution

---