LeetCode-41-缺失的第一个正数

发表于 2020-05-21 | 分类于 LeetCode | 评论数： | 热度： ℃

本文字数： 2.9k | 阅读时长 ≈ 3 分钟

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

示例 1:

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

示例 2:

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

示例 3:

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

Code

//时间复杂度O(nlogn)
//空间复杂度O(1)
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int res=1;
        //先排序
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            //因为是最小的正整数
            //遇到nums存在，则+1
            //遇到比res大，则直接返回
            if(nums[i]==res)
                res++;
            else if(nums[i]>res)
                break;
        }
        return res;
    }
};