leetcode No41. First Missing Positive
发布时间：2020-12-13 21:15:03 所属栏目：PHP教程 来源：网络整理
导读：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个缺失的正数 Algori
Question：Given an unsorted integer array,find the first missing positive integer.
For example, 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;
}
};
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |