时间轴

2026-03-12

init

题目：

P41 缺失的第一个正数

https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked

显而易见的一种解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <vector>
#include <unordered_set>
#include <climits>

using std::vector;
using std::unordered_set;

class Solution {
    public:
        int firstMissingPositive(vector<int> &nums)
        {
                int i;
                unordered_set<int> uset;
                for (int num : nums) {
                        if (num > 0)
                                uset.insert(num);
                }

                for (i = 1; i < INT_MAX; i++) {
                        if (!uset.count(i)) {
                                break;
                        }
                }

                return i;
        }
};

实际上，对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中，因此可以优化为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <vector>
#include <unordered_set>
#include <climits>

using std::vector;
using std::unordered_set;

class Solution {
    public:
        int firstMissingPositive(vector<int> &nums)
        {
                int i, n;
                unordered_set<int> uset;
                for (int num : nums) {
                        if (num > 0)
                                uset.insert(num);
                }
                n = uset.size();

                for (i = 1; i <= n + 1; i++) {
                        if (!uset.count(i)) {
                                break;
                        }
                }

                return i;
        }
};

官方题解：

仔细想一想，我们为什么要使用哈希表？这是因为哈希表是一个可以支持快速查找的数据结构：给定一个元素，我们可以在 O(1) 的时间查找该元素是否在哈希表中。因此，我们可以考虑将给定的数组设计成哈希表的「替代产品」。

实际上，对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。这是因为如果 [1,N] 都出现了，那么答案是 N+1，否则答案是 [1,N] 中没有出现的最小正整数。这样一来，我们将所有在 [1,N] 范围内的数放入哈希表，也可以得到最终的答案。而给定的数组恰好长度为 N，这让我们有了一种将数组设计成哈希表的思路：
我们对数组进行遍历，对于遍历到的数 x，如果它在 [1,N] 的范围内，那么就将数组中的第 x−1 个位置（注意：数组下标从 0 开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。

那么如何设计这个「标记」呢？由于数组中的数没有任何限制，因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质：由于我们只在意 [1,N] 中的数，因此我们可以先对数组进行遍历，把不在 [1,N] 范围内的数修改成任意一个大于 N 的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <vector>
#include <cmath>
#include <climits>

using std::vector;

class Solution {
    public:
        int firstMissingPositive(vector<int> &nums)
        {
                int i, n = nums.size();
                // 把所有小于等于 0 的变成 n+1
                for (i = 0; i < n; i++) {
                        if (nums[i] <= 0) {
                                nums[i] = n + 1;
                        }
                }

                for (i = 0; i < n; i++) {
                        if (std::abs(nums[i]) <= n && nums[std::abs(nums[i]) - 1] > 0) { // 1..=n
                                nums[std::abs(nums[i]) -1] *= -1;
                        }
                }

                for (i = 0; i < n; i++) {
                        if (nums[i] > 0) {
                                return i + 1;
                        }
                }
                return n + 1; // 1..=n
        }
};