LC 41. 缺失的第一个正数

题目描述

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

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

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

示例 1：

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

输出：3

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

输出：2

示例 3：
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）。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        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[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[i] != i + 1 and nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function swap(nums, a, b) {
    const c = nums[a];
    nums[a] = nums[b];
    nums[b] = c;
}
function firstMissingPositive(nums: number[]): number {
    const n: number = nums.length;
    for (let i: number = 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 (let i: number = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;
};

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

最后

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

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

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

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