146 lines
5.1 KiB
Markdown
146 lines
5.1 KiB
Markdown
---
|
||
tags: []
|
||
create time: 2026-05-14 15:30
|
||
---
|
||
|
||
# 缺失的第一个正数
|
||
|
||
## 题面
|
||
|
||
给你一个未排序的整数数组 `nums`，请你找出其中没有出现的最小的正整数。
|
||
|
||
**要求：** 时间复杂度 $O(n)$，只使用常数级别额外空间。
|
||
|
||
> [!example] 示例
|
||
> - **示例 1：** 输入 `[1,2,0]` → 输出 `3`，因为范围 `[1,2]` 中的数字都在数组中。
|
||
> - **示例 2：** 输入 `[3,4,-1,1]` → 输出 `2`，因为 1 存在但 2 不存在。
|
||
> - **示例 3：** 输入 `[7,8,9,11,12]` → 输出 `1`，最小正数 1 未出现。
|
||
|
||
> [!question] 💡 先思考一下
|
||
> 如果不能用哈希表、不能排序（排序是 $O(n \log n)$），你还能怎么找"缺失的最小正数"？
|
||
> 关键问题：**答案的范围是什么？**
|
||
|
||
## 思路
|
||
|
||
### 核心观察
|
||
|
||
无论数组多长，**答案一定在 `[1, n+1]` 范围内**（`n` 为数组长度）。为什么？
|
||
|
||
- 如果 `1~n` 全部出现，答案就是 `n+1`；
|
||
- 只要有任意一个缺失，答案就是那个最小的缺失值。
|
||
|
||
这就把问题从"无限正整数域"缩小到了大小为 `n` 的有限域——可以用**原地哈希**解决。
|
||
|
||
### 原地哈希（In-place Hashing）
|
||
|
||
既然答案在 `[1, n]` 或 `n+1`，我们可以让每个位置 `i` 存储值 `i+1`：
|
||
|
||
| 索引 | 0 | 1 | 2 | 3 |
|
||
|------|---|---|---|---|
|
||
| 应该存 | 1 | 2 | 3 | 4 |
|
||
|
||
也就是说：**让值为 `v` 的元素排在索引 `v-1` 的位置上。**
|
||
|
||
排列完成后，第一个不满足 `nums[i] == i+1` 的位置 `i` 对应的 `i+1` 就是答案。如果都满足，答案是 `n+1`。
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A["原始数组"] --> B{"遍历每个位置 i"}
|
||
B --> C{"nums[i] 是否合法?"}
|
||
C -->|"不在 [1,n] 或已在正确位置"| D["跳过, i++"]
|
||
C -->|"需要交换"| E["将 nums[i] 换到 nums[i]-1 位置"]
|
||
E --> F{"新位置的元素也需要处理吗?"}
|
||
F -->|"是"| G["继续检查当前位置"]
|
||
F -->|"否"| D
|
||
D --> H{i < n?}
|
||
G --> H
|
||
H -->|"是"| B
|
||
H -->|"否"| I["扫描: 找到第一个 nums[i] != i+1"]
|
||
I --> J["返回 i+1; 若全匹配则返回 n+1"]
|
||
```
|
||
|
||
### 步骤拆解
|
||
|
||
以 `nums = [3, 4, -1, 1]` 为例：
|
||
|
||
| 步骤 | 操作 | 数组状态 |
|
||
|------|------|----------|
|
||
| 初始 | — | `[3, 4, -1, 1]` |
|
||
| i=0 | nums[0]=3, 应放索引 2, 与 -1 交换 | `[-1, 4, 3, 1]` |
|
||
| i=0 | nums[0]=-1, 非法, 跳过 | `[-1, 4, 3, 1]` |
|
||
| i=1 | nums[1]=4, 应放索引 3, 与 1 交换 | `[-1, 1, 3, 4]` |
|
||
| i=1 | nums[1]=1, 应放索引 0, 与 -1 交换 | `[1, -1, 3, 4]` |
|
||
| i=1 | nums[1]=-1, 非法, 跳过 | `[1, -1, 3, 4]` |
|
||
| i=2 | nums[2]=3, 已在正确位置, 跳过 | `[1, -1, 3, 4]` |
|
||
| i=3 | nums[3]=4, 已在正确位置, 跳过 | `[1, -1, 3, 4]` |
|
||
|
||
扫描：索引 1 处 `nums[1] = -1 ≠ 2`，答案 = **2** ✅
|
||
|
||
> [!tip] ⚠️ 交换时的经典陷阱
|
||
> 交换前必须检查目标位置是否已经有正确的值，否则两个相同值会互相交换造成死循环。例如 `[1, 1]`：第一个 1 正确；第二个 1 发现索引 0 已经是 1，就不交换了。
|
||
|
||
### 复杂度分析
|
||
|
||
| 维度 | 分析 |
|
||
|------|------|
|
||
| **时间** | $O(n)$：每个位置最多被交换一次后归位，扫描也是 $O(n)$，合计两次线性遍历 |
|
||
| **空间** | $O(1)$：仅用几个指针变量，原地修改数组 |
|
||
|
||
## 代码提示
|
||
|
||
```
|
||
for i := 0 to n-1:
|
||
while nums[i] 在 [1, n] 范围内 && 不在正确位置上:
|
||
target = nums[i] - 1 // 这个值应该在的索引
|
||
swap(nums[i], nums[target]) // 把它放到正确位置
|
||
|
||
for i := 0 to n-1:
|
||
if nums[i] != i + 1:
|
||
return i + 1 // 找到了缺失的正数
|
||
|
||
return n + 1 // 1~n 都出现了
|
||
```
|
||
|
||
## 技巧
|
||
|
||
> [!summary] 套路总结
|
||
> **"第 k 个值放到第 k-1 个位置"** ——这是原地哈希的经典模式。当题目满足以下条件时可以考虑：
|
||
> 1. 数组长度为 `n`，元素范围也在 `[1, n]` 或可截断到此范围；
|
||
> 2. 要求 $O(n)$ 时间、$O(1)$ 空间；
|
||
> 3. 允许修改原数组。
|
||
|
||
相关变种题目：
|
||
- [[16-除了自身以外数组的乘积]] — 同样是原地操作的经典题
|
||
- LeetCode 448：找到所有数组中消失的数字（同样的原地哈希思想）
|
||
|
||
## 代码
|
||
|
||
```go
|
||
func firstMissingPositive(nums []int) int {
|
||
n := len(nums)
|
||
|
||
// ========== 第一步：原地哈希排列 ==========
|
||
for i := 0; i < n; i++ {
|
||
// 当 nums[i] 在 [1,n] 范围内，且不在它该在的位置上时，持续交换
|
||
// 注意判断顺序：先读值，再判范围，再防死循环
|
||
for nums[i] >= 1 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
|
||
target := nums[i] - 1
|
||
nums[i], nums[target] = nums[target], nums[i]
|
||
}
|
||
}
|
||
|
||
// ========== 第二步：找出第一个空缺 ==========
|
||
for i := 0; i < n; i++ {
|
||
if nums[i] != i+1 {
|
||
return i + 1
|
||
}
|
||
}
|
||
|
||
// 1~n 全部就位，答案是 n+1
|
||
return n + 1
|
||
}
|
||
```
|
||
|
||
> [!note] 🐛 内层 `for` vs `while`
|
||
> Go 没有 `while` 关键字，所以用 `for` 替代。逻辑是：只要条件满足就持续交换，直到当前元素归位或无法归位为止。每次成功交换至少将一个元素放到正确位置，所以整个过程中交换总次数不超过 `n` 次，不会破坏 $O(n)$ 的时间复杂度。
|