缺失的第一个正数—leetcode41

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0] 输出: 3

示例 2:

输入: [3,4,-1,1] 输出: 2

示例 3:

输入: [7,8,9,11,12] 输出: 1

提示：

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

思路：将数值与下标产生联系，将nums[i]放到索引为nums[i]-1的位置，需要注意超出数组len的值与非正数不做处理直接跳过，最后遍历判断数值是否在正确的位置即可

 

class Solution { public:int firstMissingPositive(vector<int>& nums) {int N = nums.size();for(int i=0;i<N;){//确定nums[i]的值对应的下标不越界，同时排除num[i]本身位置正确或者nums[i]应该放入的位置nums[i]-1原本就是nums[i](如[1,1])if(nums[i]>0&&nums[i]<=N&&nums[i]!=nums[nums[i]-1]){//换位置之后需要继续判断换过来的值是否在对的位置上，因此不能i++;int index = nums[i];//nums[i] = nums[index -1];nums[index -1]=index;}else{i++;}}for(int i=0;i<N;i++){if(nums[i]!=i+1){return i+1;}}return N+1;} };

 

总结

以上是生活随笔为你收集整理的缺失的第一个正数—leetcode41的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。