Leetcode:41 firstMissingPositive
数组的下标是一种天然的资源，有序，有界。在某些特殊的问题下，可以做为一种辅助信息。
问题的描述为：
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
Note:
Your algorithm should run in O(n) time and uses constant extra space.
Your algorithm should run in O(n) time and uses constant extra space. 这里面的uses constant extra space 和 O(n) 也算是一种提示吧。
具体的代码：
public int firstMissingPositive_(int[] A) {
int i = 0;
while (i < A.length) {
if (A[i] == i + 1 || A[i] <= 0 || A[i] > A.length)
i++;
else if (A[A[i] - 1] != A[i])
swap(A, i, A[i] - 1);
else
i++;
}
i = 0;
while (i < A.length && A[i] == i + 1)
i++;
return i + 1;
}
private void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}