給定一個(gè)未排序的整數(shù)數(shù)組，找出其中沒(méi)有出現(xiàn)的最小的正整數(shù)。
示例 1:
輸入: [1,2,0]
輸出: 3
示例 2:
輸入: [3,4,-1,1]
輸出: 2
示例 3:
輸入: [7,8,9,11,12]
輸出: 1
說(shuō)明:
你的算法的時(shí)間復(fù)雜度應(yīng)為O(n)讳嘱，并且只能使用常數(shù)級(jí)別的空間赋荆。
/*
思路：給定的數(shù)組nums不管里面的值是什么 結(jié)果的答案 肯定是在 1--nums.length+1中 可以看哪些有 有的話 就可以記錄 最后 遍歷 發(fā)現(xiàn)最小的沒(méi)有的
空間復(fù)雜度：O（n）
*/
class Solution {
public int firstMissingPositive(int[] nums) {
if(nums.length<=0)
return 1;
boolean[] temp = new boolean[nums.length+1];
for(int i = 0;i<nums.length;i++){
if(nums[i]>nums.length || nums[i]<=0)
continue;
else
temp[nums[i]-1] = true;
}
for(int i = 0;i<=nums.length;i++){
if(temp[i] == false)
return i+1;
}
return nums.length;
}
}
空間復(fù)雜度：O（1）
class Solution {
public int firstMissingPositive(int[] nums) {
if (nums == null || nums.length == 0) {
return 1;
}
for (int i = 0; i < nums.length; i++) {
while (0 < nums[i] && nums[i] <= nums.length && nums[i] != nums[nums[i]-1]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return nums.length + 1;
}
}
leetcode
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
