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

---