当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.041.First Missing Positive 数组中缺失的第一个正数

LeetCode.041.First Missing Positive 数组中缺失的第一个正数

题目描述

41 First Missing Positive
https://leetcode-cn.com/problems/first-missing-positive/

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:
Your algorithm should run in O(n) time and uses constant extra space.


解题过程

相似题目
LeetCode.448.Find All Numbers Disappeared in an Array 数组中消失的数
LeetCode.442.Find All Duplicates in an Array 数组中所有重复的数
LeetCode.645.Set Mismatch 找出数组中重复的数和缺失的数
LeetCode.041.First Missing Positive 数组中缺失的第一个正数

在做完 448、442、645 题后,41题仔细想了想就知道怎么做了,但如果没有之前的做题经历,直接做41题,肯定是想不出来的,这里面有一个循序渐进的思考过程:先想到数组下标哈希法,但不满足条件,再想怎么处理数据让他满足条件。

首先要搞清楚,长度为n的整数数组中缺失的最小正数肯定在 1 到 n+1 之间,我们只需要判断 1到n 在不在数组中即可。
用数组下标哈希法在原数组上标识 1到n 是否存在,对于负数、0、大于等于n+1 的数都可以忽略不管。
因为原数组中可能有负值和0,所以不能直接使用取反来标识存在,先把原数组处理下,把0和负值都替换为不影响判断的任意大于等于 n+1 的数。

时间复杂度 O(n),空间复杂度 O(1)

private static class SolutionV2020 {
    public int firstMissingPositive(int[] nums) {
        if (null == nums || nums.length == 0) {
            return 1;
        }
        // 把所有非正数替换为 n+1
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) {
                nums[i] = nums.length + 1;
            }
        }
        // 用数组下标法把 1≤a[i]≤n 的数标为已存在
        for (int i = 0; i < nums.length; i++) {
            if (Math.abs(nums[i]) >= 1 && Math.abs(nums[i]) <= nums.length) {
                nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1]);
            }
        }
        // 找第一个不存在(值为正)的下标,就是缺失的最小正数,找不到则结果就是n+1
        int i = 0;
        for (; i < nums.length; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return i + 1;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_041_FirstMissingPositive.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_041_FirstMissingPositive.java


上一篇 LeetCode.260.Single Number III 数组中只出现一次的数3

下一篇 LeetCode.645.Set Mismatch 找出数组中重复的数和缺失的数

阅读
评论
569
阅读预计2分钟
创建日期 2020-02-14
修改日期 2020-06-27
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论