05
05/2015
[LeetCode] First Missing Positive
First Missing Positive
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.
解题思路:
这道题非常不错，最直接想到的办法就是（1）排序，然后扫描，或者（2）用一个数组来记录已经出现过的值。但是题目要求时间复杂度为O(n)，空间复杂度为常数，（1）方法时间复杂度为O(nlogn)，（2）方法空间复杂度为O（n），均不符合要求。
一个非常impressive的办法是交换的思想，将值为a的数移动到nums[a-1]下（若a在允许的范围之内）。最后再扫描一遍数组，发现值不等于其下标+1的就是所求。
需要注意的有两点：
（1）可能会有多个相同的值。若两个值相同，则不交换
（2）注意下标是从0开始的，而值是从1开始的。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int len = nums.size();
for(int i=0; i<len; ){
if(nums[i]>0 && nums[i]<=len && nums[i]!=i+1 && nums[i]!=nums[nums[i]-1]){
swap(nums, i, nums[i]-1);
}else{
i++;
}
}
for(int i=0; i<len; i++){
if(i + 1 != nums[i]){
return i + 1;
}
}
return len + 1;
}
private:
void swap(vector<int>& nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
};
0 条评论