美文网首页
LeetCode-First Missing Positive

LeetCode-First Missing Positive

作者: 圣地亚哥_SVIP | 来源:发表于2018-07-12 19:19 被阅读0次

题目要求:
在一个给定的整数数组中,检索不在此数组的最小整数;
Example 1:

Input: [3,4,-1,1] Output: 2
解题思路:

数组的长度为N,其最多存储N个正整数。如果整数中存在大于N的数,或小于等于0的数。则数组中小于等于N的整数的个数肯定小于N。则小于等于N且大于0的整数无法构成连续数列。因此,所求的数必然要小于等于N。因此我们只需将大于0且小于等于N的数,放在0~N-1对应的位置即可。第一个不对应的点便是所求的数。代码如下:

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int i=0;
        int res =nums.size()+1;
        for (;i<nums.size();){
             //注意此处,进行swap后,nums[nums[i]-1]在对应的位置,但是nums[i]不一定和i对应。因此,i不能自增,还需要判断交换到i处的数是否和i对应
            if (nums[i]!=i+1 && nums[i]>0 && nums[i]<=nums.size() && nums[nums[i]-1] != nums[i]){
                
                auto tmp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = tmp;
            }else{ 
                i++;
            }
        }
        for (i=0;i<nums.size();++i){
            //cout<<"i: "<<i<<"; "<<nums[i]<<endl;
            if (nums[i]!= i+1){
                res = i+1;
                break;
            }
        }
        return res;
    }
};

相关文章

网友评论

      本文标题:LeetCode-First Missing Positive

      本文链接:https://www.haomeiwen.com/subject/bawrpftx.html