41. First Missing Positive
41. First Missing Positive
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
开一个len+2长度的辅助数组,思想类似于哈希,初始化为0
遍历一遍数组,然后,把nums数组的数对应到辅助数组对应的值变为1
这里有个技巧,就是只开len+2长度就行了,你想下,如果数组只有5位,那么最小的正整数最理想的情况下就只能是6,所以数组中有大于6的数都可以忽略掉
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
if(nums.size()==0){
return 1;
}
int len = nums.size();
vector<int> a(len+2,0);
for(int i = 0;i < len; ++i) {
if(nums[i]<=0 || nums[i]>len){
continue;
}
a[nums[i]]=1;
}
int pos=0;
for(int i = 1 ;i <= len+1; ++i ){
if(a[i]==0){
pos = i;
break;
}
}
return pos;
}
};