巧妙使用桶排序思想实现 O(n) 最优解

本文正在参加「Java主题月 – 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
– $2^{31}$ <= nums[i] <= $2^{31}$ – 1

桶排序

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

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

基本思路为：

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

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

遍历 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(1)$

实战技巧

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

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

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

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

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

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

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

$O(n\log{n})$ 解法代码：

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;
    }
}
复制代码