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.
Misunderstanding on the problem:
find the first missing positive, not the missing consecutive number !!!
i.e. 7 5 8 return 1 not 6
Solution:
zero based:
int firstMissingPositiveAnd0(int A[]) {
int n = A.length;
for (int i = 0; i < n; i++) {
// when the ith element is not i
while (A[i] != i) {
// no need to swap when ith element is out of range [0,n]
if (A[i] < 0 || A[i] >= n)
break;
//handle duplicate elements
if(A[i]==A[A[i]])
break;
// swap elements
int temp = A[i];
A[i] = A[temp];
A[temp] = temp;
}
}
for (int i = 0; i < n; i++) {
if (A[i] != i)
return i;
}
return n;
}
one based:
public int firstMissingPositive(int[] A) {
int n = A.length;
for (int i = 0; i < n; i++) {
while (A[i] != i + 1) {
if (A[i] <= 0 || A[i] >= n)
break;
if(A[i]==A[A[i]-1])
break;
int temp = A[i];
A[i] = A[temp - 1];
A[temp - 1] = temp;
}
}
for (int i = 0; i < n; i++){
if (A[i] != i + 1){
return i + 1;
}
}
return n + 1;
}