Leetcode | 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.

在原數組上做交換，把每個正數放到正确的位置上。因為是求正數。是以0這個位置上放的應該是1. 

1.如果A[i]==i+1,已經放在正确的位置上了，那麼可以處理下一個數；

2. 如果A[i]不在[1,n]這個範圍内，也不用處理，放在那裡就行；

3. 如果A[i]==A[A[i]-1]，也就是說，在該位置上已經有正确的數了，A[i]這個是重複的，那麼也不用處理；

4.

然後就是交換A[i]和A[A[i]-1]，交換一次，A[i]是放到正确的位置了，可是目前交換過來的數（原先的A[A[i]-1]）可能不在正确的位置上，這個數也要處理，否則因為i向前，這個數永遠也不會被正确放置了。是以這裡i不能向前，直到交換之後A[i]不能再動了。是以這裡要先i--，再i++。