首页 > 其他 > 详细

缺失的第一个正数

时间:2018-10-21 10:02:35      阅读:78      评论:0      收藏:0      [点我收藏+]

题目描述

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

  • 示例 1:
    输入: [1,2,0]
    输出: 3
  • 示例 2:
    输入: [3,4,-1,1]
    输出: 2
  • 示例 3:
    输入: [7,8,9,11,12]
    输出: 1

  • 说明:
    你的算法的时间复杂度应为 \(\mathcal{O}(n)\),并且只能使用常数级别的空间。

我的解答

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    int max = 0;
    for (int i = 0; i < n; i++)
        if (nums[i] > max) max = nums[i];
    bool flags[max+2] = {false};
    for (int i = 0; i < n; i++) {
        int num = nums[i];
        if(num > 0) flags[num] = true;
    }
    if (n > 0) {
        for (int i = 1; i <= max+1; i++)
            if (!flags[i]) return i;
    } else
        return 1;
}

缺失的第一个正数

原文:https://www.cnblogs.com/4thirteen2one/p/9823688.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!