class Solution {
public:
int firstMissingPositive(int A[], int n) {
for(int ii = 0; ii < n; ++ii) {
while (A[ii] != ii + 1 ) {
if (A[ii] <= 0 || A[ii] > n || A[ii] == A[A[ii] - 1]) {
A[ii] = -1;
break;
}
swap(A, ii, A[ii]-1);
}
}
for (int ii = 0; ii < n; ++ii) {
if (A[ii] != ii+1) return ii+1;
}
return n+1;
}
void swap(int A[], int here, int other) {
int temp = A[here];
A[here] = A[other];
A[other] = temp;
return;
}
};
No comments:
Post a Comment