very simple solution. The procedure is as following:

- scan through the array
- if the number should be at a position in front of the current position (smaller than the current index), swap the number to the correction position; if the new number at the current position is still smaller than the current index, keep on swapping
- Now the array should be [1, 2, 3, ...] until the first missing positive number, find this number.

I've tested many cases, the numbers of swaps are always smaller than the length of the array. Any one help me to prove that this algorithm is O(n) time.

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