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.
*/
public class Solution {
public int firstMissingPositive(int[] A) {
if(A.length == 0)
return 1;
for(int i = 0; i < A.length; i++){
if(A[i] > 0 && A[i] - 1 < A.length && A[i] - 1 != i && A[i] != A[A[i] - 1]) {
int t = A[A[i] - 1];
A[A[i] - 1] = A[i];
A[i] = t;
i--;
}
}
for(int j = 0; j < A.length; j++){
if(A[j] - 1 != j)
return j + 1;
}
return A.length + 1;
}
}