巧妙使用桶排序思想实现 O(n) 最优解｜Java 刷题打卡

题目描述

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

Tag : 「桶排序」

给你一个未排序的整数数组 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
• -2312^{31}231 <= nums[i] <= 2312^{31}231 - 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]。

2. 遍历 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;
    }
}
复制代码

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

实战技巧

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

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

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

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

排序的复杂度为 O(nlog⁡n)O(n\log{n})O(nlogn)；找答案的过程需要枚举 [1, n]，然后通过「二分」找当前的枚举值是否在排序数据中，复杂度为

O(nlog⁡n)O(n\log{n})O(nlogn)。因此整体复杂度为 O(nlog⁡n)O(n\log{n})O(nlogn)。

而文字要求我们使用 O(n)O(n)O(n) 复杂度的解法。这时候我们基本上可以不看数据范围就可以确定 O(nlog⁡n)O(n\log{n})O(nlogn) 能做。

因为 O(nlog⁡n)O(n\log{n})O(nlogn) 和 O(n)O(n)O(n) 并没有差多少，哪怕数据范围出到极限 10710^7107。log107log{10^7}log107 = 23，数值非常小，O(nlog⁡n)O(n\log{n})O(nlogn) 可以等效看做一个常数计算为 23 的 O(n)O(n)O(n) 解法。何况本题的数据范围只有 300，可以说怎么做都行。

O(nlog⁡n)O(n\log{n})O(nlogn) 解法代码：

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 上 O(nlog⁡n)O(n\log{n})O(nlogn) 解法和 O(n)O(n)O(n) 解法的执行用时没有差别。

最后

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

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

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

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