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.
java代码如下:
public class Solution {
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;
}
}
转载请注明原文地址: https://ju.6miu.com/read-677820.html