首页 > 代码库 > 41. First Missing Positive
41. 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.
解题思路:本题的核心思想就是将x放置到nums[x-1]的位置上去,然后从头开始遍历数组即可。但是把数交换过去和只是标记符合条件的数存不存在的两种选择衍生出了两种不同的解法。
解法一:并不交换,而用数的正负性来表示数的存在与否。具体地说,如果x属于区间[1,n],将x-1处的数变成负数即可。具体代码如下:
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n=nums.size(); for(int i=0;i<n;i++){ if(nums[i]>=1&&nums[i]<=n)continue; nums[i]=n+1; } for (int i=0;i<n;i++) { int ori=abs(nums[i]); if (ori<=n)nums[ori-1]=-abs(nums[ori-1]);//nums[i] < 0 means i+1 exist } for(int i=0;i<n;i++) if(nums[i]>=0)return i+1; return n+1; } };
解法二:每次都把[1,n]区间内的x移动到nums[x-1]处
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n=nums.size(); for(int i=0;i<n;i++){ while(nums[i]>0&&nums[i]<=n&&nums[i]!=nums[nums[i]-1]) swap(nums[i],nums[nums[i]-1]); } for(int i=0;i<n;i++) if(i+1!=nums[i])return i+1; return n+1; } };
41. First Missing Positive
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。