求出缺失的第一个正数(C++(中等学习区))

tech2023-07-15  103

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

示例 1:

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

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

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

解: 先把大于0的数都拿出来放到一个容器中,然后排序,排序后将每一个数组中的数和它的序号比较,把第一个不相等的输出来,请问哪里有问题????执行都是正确的,但是每次提交都会出错,想不通为什么?

class Solution { public: int firstMissingPositive(vector<int>& nums) { vector<int>v; vector<int>v1; for(int i=0; i<nums.size();i++) { if(nums[i]>0) { v.push_back(nums[i]); } } sort(v.begin(), v.end()); for(int i=0; i<v.size();i++) { if(v[i]!=i+1) { v1.push_back(i+1); break; } } if(v1.empty()) { v1.push_back(v[v.size()-1]+1); } return v1[0]; } };

后来想通了:

解题思路

此处撰写解题思路 首先考虑特殊情况,数组为空,数组全部是负数,数组全部是0,这三种都要输出1,接着对于正常情况,先把大于0的数都拿出来放到一个容器中,然后排序,排序后将每一个数组中的数和它的序号比较,把第一个不相等的输出来。但这样有一个问题就是,如果有重复的两个数怎么办?比如 1122334,这个最小的正数是5,但是它会输出2,所以把大于0的数放到set容器里面,这样就保证了不会重复。最后如果出现12345这种,就把最后一个加1输出来。

代码

class Solution { public: int firstMissingPositive(vector<int>& nums) { int n=nums.size(); if(n==0) return 1; int count=0; for(int i=0; i<nums.size();i++) { if(nums[i]<0||nums[i]==0) { count++; } } if(count==nums.size()) return 1; set<int>v; vector<int>v1; for(int i=0; i<nums.size();i++) { if(nums[i]>0) { v.insert(nums[i]); } } //sort(v.begin(), v.end()); int i=0; for(set<int>::iterator it=v.begin(); it!=v.end(); it++) { if(*it != i+1) { v1.push_back(i+1); break; } i++; } if(v1.empty()) { v1.push_back(*(v.end())+1); } return v1[0]; } };
最新回复(0)