題目描述
給出一個無序的整數(shù)型數(shù)組坊萝，求不在給定數(shù)組里的最小的正整數(shù)
例如：
給出的數(shù)組為[1,2,0] 返回3,
給出的數(shù)組為[3,4,-1,1] 返回2.
你需要給出時間復雜度在O(n)之內并且空間復雜度為常數(shù)級的算法
分析
- 將數(shù)組中所有負數(shù)和0，替換成MAX_VALUE
- 一個n維數(shù)組钻哩，first-miss-positive 一定不大于 n+1
- 遍歷一遍數(shù)組屹堰，遍歷過程中：
- 數(shù)組下標為 i時 ，A[i] 如果不是MAX_VALUE街氢，而且在數(shù)組下標范圍內出現(xiàn)（如果大于數(shù)組的長度n扯键，first-miss-positive也一定不是這個數(shù)）。將對應位置的A[A[i]-1]珊肃，置為負數(shù)荣刑。表明A[i]出現(xiàn)于數(shù)組中馅笙。
- 再次遍歷數(shù)組的時候，如果某下標j出現(xiàn) A[j] > 0,情況時厉亏，說明數(shù)字j+1沒有出現(xiàn)過董习。
java 代碼
public class Solution {
public int firstMissingPositive(int[] A) {
if(A == null || A.length == 0){return 1;}
for(int i = 0; i < A.length; i++){
if(A[i] <= 0){
A[i] = Integer.MAX_VALUE;
}
}
for(int i = 0; i< A.length; i++){
int temp = Math.abs(A[i])-1;
if(temp < A.length){
A[temp] = -Math.abs(A[temp]);
}
}
for(int i = 0; i < A.length ; i++){
if(A[i] > 0){
return i+1;
}
}
return A.length + 1;
}
}
