给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。
示例 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输出来。