leetcode-go/普通数组/17-缺失的第一个正数.md

---
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)$ 的时间复杂度。