|
因为所要求的时间复杂度是O(n),且空间复杂度是常数，所以我们每个位置对应一个正整数 第一个位置是1 第二个位置是2 以此类推
先对数组使用交换，之后再访问数组 当位置与正整数不对应时返回结果
int firstMissingPositive(std::vector<int>& nums) {
int temp=0;
int i=0;
int t=0;
if(nums.size()==0)
return 1;
while(i!=nums.size()){
if(nums[i]==t+1||nums[i]<=0||nums[i]>nums.size()) {
i++;
t++;
}
else{
if(nums[i]!=nums[nums[i]-1]){
temp=nums[nums[i]-1];
nums[nums[i]-1]=nums[i];
nums[i]=temp;
}
else{
i++;
t++;
}
}
}
int j=0;
for(;j<nums.size();j++){
if(nums[j]!=j+1)
return j+1;
}
return j+1;
}
| 
转播
