leetcode No41. First Missing Positive
來源：程序員人生 發布時間：2016-10-06 09:42:52 閱讀次數：2428次
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;
}
};
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
