leetcode No41. First Missing Positive
来源：程序员人生 发布时间：2016-10-06 09:42:52 阅读次数：2060次
Question：
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,⑴,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
求第1个缺失的正数
Algorithm：
传统的做法，排序然后遍历找到nums[i]!=i+1的元素，复杂度O(nlogn)
可以用bucket sort思想，再开辟1个数组B，把元素作为B的下标寄存在数组B中，然后遍历找到nums[i]!=i+1，复杂度为O(n)，但是空间复杂度需要O(n)。
我们可以在nums中做类似桶排序的工作，如果nums[i]!=i+1，则交换nums[i]和下标为nums[i]⑴的元素，如果nums[i]不在1~n中则不动。
Accepted Code：
class Solution {
public:
void swap(int &x,int &y)
{
int tmp=x;
x=y;
y=tmp;
}
int firstMissingPositive(vector<int>& nums) {
int i=0;
while(i<nums.size())
{ //nums[i]!=nums[nums[i]⑴]是避免元素相等的时候出现死循环
if(nums[i]!=i+1 && nums[i]>=1 && nums[i]<=nums.size() && nums[i]!=nums[nums[i]⑴])
swap(nums[i],nums[nums[i]⑴]);
else i++;
}
for(int i=0;i<nums.size();i++)
if(nums[i]!=i+1)
return i+1;
return nums.size()+1;
}
};
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
