LEETCODE 41. First Missing Positive 解题思路分析

题目大意:

缺失的第一个正数

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

示例 1:

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

示例 2:

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

示例 3:

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

说明:

你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=41

解题思路分析:

缺失的第一个正数,就是缺少的最小的那个正数,我们应该先明确这个正数的取值范围,最小值应该是1,也就是说如果数组中不存在1的话,那么返回值应该是1。那么最大值的可能是多少呢?假设数组中存在n个数字,最极端的情况是这n个数字分别是1到n,因此,此时缺失的最小正数应该是n+1,除此以外,不论1到n之间缺少哪个数字,该数字一定是小于n+1的。这样,我们就将返回结果的范围缩小到了数字区间[1, n](n为数组长度)之间。

我们定义一个boolean型数组has[],数组长度为n+1,循环一遍数组,记录数字1到n之间哪些数字出现过,然后再循环has,当has[i]为false时,表示数字i没有出现过,可返回i。如果has数组中的数字全都出现过,那么返回n+1。

实现代码:

public int firstMissingPositive(int[] nums) {
    // 记录出现过的数字
    boolean[] has = new boolean[nums.length+1];
    for(int n : nums){
        if(n<=0 || n>=has.length) continue;
        has[n]=true;
    }
    // 找到最小的没有出现过的数字
    for(int i=1;i<has.length;i++){
        if(!has[i]) return i;
    }
    // 1到n全出现过时,返回n加1,即has数组长度
    return has.length;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for First Missing Positive.

Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for First Missing Positive.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-41-first-missing-positive-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。