【刷穿 LeetCode】41. 缺失的第一个正数（困难）

题目描述

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

进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

• 0 <= nums.length <= 300
• -2^31 <= nums[i] <= 2^31 - 1

桶排序解法

令数组长度为 n，那么答案必然在 [1, n + 1] 范围内。

因此我们可以使用「桶排序」的思路，将每个数放在其应该出现的位置上。

基本思路为：

1. 按照桶排序思路进行预处理：保证 1 出现在 nums[0] 的位置上，2 出现在 nums[1] 的位置上，…，n 出现在 nums[n - 1] 的位置上。不在 [1, n] 范围内的数不用动。

例如样例中 [3,4,-1,1] 将会被预处理成 [1,-1,3,4]。

1. 遍历 nums，找到第一个不在应在位置上的 [1, n] 的数。如果没有找到，说明数据连续，答案为 n + 1

例如样例预处理后的数组 [1,-1,3,4] 中第一个 nums[i] != i + 1 的是数字 2（i = 1）。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }   
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
    void swap(int[] nums, int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
}

• 时间复杂度：每个数字应该被挪动的数都会被一次性移动到目标位置。复杂度为

• 空间复杂度：

实战技巧

还记得最早我在 【刷穿 LeetCode】4. 寻找两个正序数组的中位数 跟你说过，对于一些从文字上限制我们的题目，我们应该如何分析能否采用别的做法来 AC。

这对于比赛和机试，这种要求我们尽快 AC 的场景来说，尤为重要。

总的来说，你可以根据直观解法的时空复杂度、文字限制的时空复杂度和数据范围等几个方面来判断。

对于本题而言，我们可以很容易想到先排序，再遍历的做法：

排序的复杂度为

；找答案的过程需要枚举 [1, n]，然后通过「二分」找当前的枚举值是否在排序数据中，复杂度为

。因此整体复杂度为

。

而文字要求我们使用

复杂度的解法。这时候我们基本上可以不看数据范围就可以确定

能做。

因为

和

并没有差多少，哪怕数据范围出到极限

。

= 23，数值非常小，

可以等效看做一个常数计算为 23 的

解法。没有一个支持多语言的 OJ 卡常可以做到

超时，而

能过。何况本题的数据范围只有 300，可以说怎么做都行。

PS. 复杂度分析本身就是渐进分析，23 作为常数可以说一点都不大，大家不要被直觉骗了。

解法代码：

class Solution {
    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 1; i <= n; i++) {
            if (Arrays.binarySearch(nums, i) < 0) return i;
        }
        return n + 1;
    }
}

你会发现，在 LeetCode 上

解法和

解法的执行用时没有差别。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.41 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 41/1916 。

为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。