分析

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入： nums = [1,2,0] 输出： 3 解释： 范围 [1,2] 中的数字都在数组中。

示例 2：

输入： nums = [3,4,-1,1] 输出： 2 解释： 1 在数组中，但 2 没有。

示例 3：

输入： nums = [7,8,9,11,12] 输出： 1 解释： 最小的正数 1 没有出现。

---

题解

原地负号标记

核心思想

步骤 1：清理干扰项

数组里的负数、0 对找最小正整数没有意义，还会干扰 “负号标记”。

把所有 $\le0$ 的元素统一改成 $n+1$。

$n+1$ 大于数组长度，后面会直接忽略，相当于无效占位。

步骤 2：用负号做 “存在标记”

规则：如果数字 val 出现过，就把下标 val‑1 的元素变成负数。

下标位置为负 ⇒ 代表对应数字存在；下标位置为正 ⇒ 代表对应数字缺失。

举例子：数组出现数字3

• $val=3$，对应下标 $3-1=2$
• 将 nums[2] 置为负数，表示：数字 3 已经存在

⚠️两个关键点：

1. 取abs(x)：数组元素可能已经被别的数字改成负数，我们只关心原本的数值。
2. 写 -abs(nums[val‑1])：防止同一个数字多次出现，反复取负变回正数，标记失效。

我们不改原元素本身，只是去修改它对应的下标位置。

步骤 3：扫描找答案

从头遍历数组：

• 遇到第一个 nums[i]>0：下标i没有被标记为负，代表数字 $\boldsymbol{i+1}$ 缺失，直接返回 $i+1$。
• 全部都是负数：说明$1\sim n$全部出现，返回 $n+1$。

代码

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(auto &x: nums) {
            if(x <= 0) x = n + 1;
        }
        for(auto &x: nums) {
            int val = abs(x);
            if(val >= 1 && val <= n) {
                nums[val - 1] = -abs(nums[val - 1]);
            }
        }
        for(int i = 0; i < n; i++) {
            if(nums[i] > 0) return i + 1;
        }
        return n + 1;
    }
};

时间复杂度：$O(n)$，三轮线性遍历 空间复杂度：$O(1)$，原地修改输入数组，无额外数组

原地哈希（置换）

核心思想

前提结论：长度为 n 的数组，答案一定在 $[1,\ n+1]$。

我们希望：数字 x 应当存放在下标 (x-1) 的位置。

• $x=1$ → 下标 0
• $x=2$ → 下标 1
• …
• $x=n$ → 下标 $n-1$

把 $1\sim n$ 的数字 “归位” 到自己对应的下标；大于 n、负数、0 不用管，它们不可能成为答案。

核心规则

对每个位置 i：

如果 $nums[i]$ 的值 x 满足：$1\le x \le n$，并且 nums[x‑1] != x，就交换：

swap(nums[i], nums[x‑1])

交换之后，x 去到它正确的下标 $x‑1$。

⚠️交换过来的新元素，依然有可能需要归位，所以用 while，不是 if。

为什么 while，不能 if

交换完成后，当前 i 位置来了一个新数字，这个新数字也可能属于 $1\sim n$，也需要放到正确位置；if 只会处理一次，while 会反复处理直到当前位置的数不需要再交换。

为什么判断 nums[x‑1] != x

防止重复元素死循环。

例：[2,2]，$x=2$，目标下标是 1，nums[1]已经等于 2，如果还 swap，会原地无限交换。这个条件阻断死循环。

代码

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[nums[i] - 1] != nums[i]) {
                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;
    }

时间复杂度：$O(n)$，每个元素最多被交换一次，while 总执行次数≤n 空间复杂度：$O(1)$，原地修改输入数组

两种算法对比

方法	核心思路	优点	缺点
负标记法	数值不动、下标打正负标记	无while、无死循环、代码稳健	破坏原数组符号信息
原地置换法	数值归位、下标严格映射	数组语义清晰、直观易懂	需处理重复元素防死循环

---

41. 缺失的第一个正数 - 力扣（LeetCode）