【综合笔试题】难度 2/5，一道笔试 O(nlogn)，面试 O(n) 的经典题

题目描述

这是 LeetCode 上的「41. 缺失的第一个正数」，难度为 Hard。

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

进阶：你可以实现时间复杂度为

并且只使用常数级别额外空间的解决方案吗？

示例 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
• -

<= nums[i] <=

- 1

桶排序

令数组长度为 n，那么答案必然在

范围内。

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

基本思路为：

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

范围内的数不用动。 例如样例中 [3,4,-1,1] 将会被预处理成 [1,-1,3,4]。

1. 遍历 nums，找到第一个不在应在位置上的

的数。如果没有找到，说明数据连续，答案为 n + 1

例如样例预处理后的数组 [1,-1,3,4] 中第一个

的是数字 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;
    }
}

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

• 空间复杂度：

实战技巧

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

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

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

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

排序的复杂度为

；找答案的过程需要枚举

，然后通过「二分」找当前的枚举值是否在排序数据中，复杂度为

。因此整体复杂度为

。

而文字要求我们使用

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

能做。

因为

和

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

。

= 23，数值非常小，

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

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

代码：

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 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

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

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

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