企业官网建设流程全解析

第一次在刷题平台上看到“寻找缺失的第一个正数”这道题的时候，我的第一反应是：这不就是先排序再从头扫一遍的事吗？但再一看题目的限制条件，“原地修改数组，只能使用常数级别额外空间”，瞬间就没了底气。如果允许用哈希表，这题甚至称不上中等难度；但一旦加上原地这个约束，它立刻变成了一道考察算法思维和边界控制能力的典型题目，也就是标题里说的“原地哈希”。

这道题的核心，不是让你真的去实现一个哈希表，而是让你意识到：数组本身可以被改造成一张哈希表。下标就是键，元素就是值，利用交换把每个数字送回它该在的位置，最后线性扫描就能拿到答案。整个过程不需要额外分配 O(n) 的空间，只需要一个临时变量做交换，完美命中题目的复杂度要求。

这篇文章我会从题目边界、核心思想、代码实现、正确性证明、踩坑经验到变体题型，完整拆解这一经典解法。无论你是刚开始刷题的新手，还是准备面试的进阶选手，这篇文章都能让你把这道题吃透，以后遇到同类问题直接形成条件反射。

1. 先搞清楚题目到底在为难我们什么

1.1 题目原意与边界条件

给你一个未排序的整数数组nums，请找出其中没有出现的最小的正整数。听起来很简单对不对？但有两个额外限制：时间复杂度必须是 O(n)，空间复杂度必须是 O(1)。

举个例子：

• 输入[1,2,0]，答案是3。因为 1 和 2 都在，3 不在。
• 输入[3,4,-1,1]，答案是2。因为 1 在，2 不在。
• 输入[7,8,9,11,12]，答案是1。因为最小的正整数 1 就没出现过。

这里有几个关键点需要先明确：

• 数组中的元素可能包含负数、零、重复元素，也可能包含非常大甚至超出数组长度的正数。
• 题目要找的不是“最大连续区间”，也不是“数组里缺失的最大值”，而是从 1 开始往上数，第一个“空了”的正整数。
• 数组长度记为 n，那么答案一定落在[1, n+1]这个区间内。为什么？因为如果 1 到 n 全都出现过，那么 n+1 就是缺失的最小正整数；否则至少有一个 1 到 n 之间的数缺失，答案就在中间。

这个结论是整个原地哈希方案的基石。它告诉我们：我们根本不需要关心那些大于 n 的数字，也不需要关心 0 和负数，因为它们对答案没有任何影响。

1.2 常规思路为什么会被“原地”卡住

我先说说大多数人看到这题的第一反应，以及为什么每个反应都会撞墙。

方案一：先排序，再遍历。

排序后从头扫，用一个变量expected = 1记录当前期望的正整数，遇到nums[i] == expected就expected++，最后返回expected。这个思路很好理解，但排序的时间复杂度是 O(n log n)，除非题目要求放宽到 O(n log n)，否则直接告辞。

方案二：用哈希集合。

把所有数组元素塞进一个HashSet，然后从 1 开始枚举，看哪个数字不在集合里。时间复杂度 O(n)，空间复杂度 O(n)。虽然时间达标了，但额外空间不符合 O(1) 的要求。

如果你在面试中说“我用一个额外的哈希表”，面试官大概率会追问：“能不能不用额外空间？”这道题的全部考点就落在这里。

方案三：用一个长度为 n 的布尔数组做标记。

扫描数组，把每个值在[1,n]范围内的数字对应的布尔位标记为 true，最后找第一个 false 的位置。这个思路在时间上是 O(n)，但空间又变成了 O(n)，同样不符合要求。

你会发现，常规方案总是在“时间达标但空间超标”和“空间达标但时间超标”之间摇摆。而原地哈希正好同时满足两个约束，它以 O(1) 空间换来了 O(n) 时间，代价是我们必须允许修改原数组。题目没有禁止这一点，这其实就是题目的暗示。

2. 原地哈希的核心思想：把数组下标当成哈希桶

2.1 为什么能做到 O(1) 空间

要理解原地哈希，先想清楚哈希表是什么：它是一个从键到值的映射。通常我们用额外的内存来存储这个映射关系，比如链表节点、红黑树节点、开放的数组桶等等。

但这里有一个极大的便利条件：答案的范围被限制在[1, n+1]，而数组长度恰好是 n。

这意味着一共只有 n 种可能的“答案候选值”。而我们刚好有一个长度为 n 的数组。那么问题来了：能不能让数组的第 i 个位置，去“代表”数字 i+1 是否出现？

完全可以。

我们可以定这样一个规则：如果数组下标 i 上的值恰好等于 i+1，就说明数字 i+1 存在于数组中。例如nums[0] == 1说明 1 存在，nums[1] == 2说明 2 存在，以此类推。

这样，整个数组就变成了一张“哈希表”，下标是键，元素值就是它应该待在哪个桶里的标记。由于我们用的是数组本身，不需要额外分配空间，因此 O(1) 额外空间自然满足。

2.2 数字与下标的映射关系怎么定

我们在代码中习惯使用 0-based 下标，所以定义一个“正确位置”的规则：

• 数字k应该出现在下标k-1处。

换句话说：

• 1 应该放到nums[0]
• 2 应该放到nums[1]
• 3 应该放到nums[2]
• 以此类推，k应该放到nums[k-1]

那么，什么情况下这个数字才“有地方可去”？只有当1 <= k <= n时，k-1才是一个合法的数组下标。如果k <= 0，下标为负，非法；如果k > n，下标超出数组长度，放不下。这两类数字我们不管，直接跳过。

举个例子。假设n=5，数字 3 应该放在下标 2 处。而数字 6 呢？它没有对应的位置，因为数组长度只有 5，我们只关心 1 到 5 是否齐全。如果 1 到 5 全部齐全，答案就是 6，也就是 n+1。

这就是整个映射关系的本质：数组的每一个可用下标，都对应一个“需要被检查是否存在的正整数”。

2.3 哪些数可以直接忽略

在交换归位的过程中，我们只需要处理满足1 <= nums[i] <= n的数字。对于以下三种情况，直接跳过：

1. 负数：比如 -2，它不可能成为答案，也不需要放进某个下标。
2. 零：0 不是正整数，跳过。
3. 大于 n 的正数：比如 n+5，它不在我们的检查范围内，因为答案最大也不可能超过 n+1，当 1 到 n 都齐全时，答案就是 n+1，这个 n+5 根本不会影响判断。

但注意，“跳过”不等于“删除”。交换过程中，这些无关数字可能会被换到数组的各个位置，但它们不会进入目标位置，最终只会留在某些“错误位置”上。第二轮扫描时，我们只要找到第一个nums[i] != i+1的位置，就能判断出缺失的数字。

这里再补充一个容易误解的点：第一轮结束后，数组中仍然可能存在负数、零、大于 n 的数，但那不重要。因为我们需要找的是一个“空缺的位置”，只要某个位置上的值不等于它应放的值，就说明这个位置对应的数字缺失了。

3. 算法流程拆解：两个循环背后的逻辑

3.1 第一轮：把每个数“送回”它该待的位置

第一轮遍历数组，我们的目标不是排序，而是让所有“可以被归位”的数字都回到自己的“正确位置”。

具体操作是这样：用一个循环变量i从 0 开始遍历数组，对于当前下标i：

• 记当前值为v = nums[i]。
• 如果v在[1, n]范围内，且v目前没有待在正确位置（即nums[v-1] != v），那就交换nums[i]和nums[v-1]。
• 如果v不在范围内，或者v已经在正确位置上，就把i加 1，继续处理下一个位置。

这里有一个极其关键的点：交换之后，当前位置i上会出现一个新的数字，这个新数字也可能需要归位，所以不能立刻把i加 1，而是要继续检查当前i位置。

因此，第一轮应该用while循环，而不是用for循环配合一次if交换。这也是很多初学者的第一个大坑。

我们看一个运行过程，以nums = [3, 1, 4, 2, 0]为例：

• 初始状态：[3, 1, 4, 2, 0]，i=0，v=3，合法，目标下标2，nums[2]=4 != 3，交换得到[4, 1, 3, 2, 0]。
• 此时i=0位置的值变成 4，v=4，合法，目标下标3，nums[3]=2 != 4，交换得到[2, 1, 3, 4, 0]。
• 继续检查i=0，当前值变成 2，合法，目标下标1，nums[1]=1 != 2，交换得到[1, 2, 3, 4, 0]。
• 现在i=0位置的值为 1，已经在正确位置，i++。之后i=1位置值为 2，正确；i=2位置值为 3，正确；i=3位置值为 4，正确；i=4位置值为 0，不在[1,n]，跳过，i变成 5，循环结束。

经过第一轮，数组变成[1, 2, 3, 4, 0]。1 到 4 全部归位，0 留在最后。

3.2 第二轮：扫描找出第一个“座位空着”的位置

第一轮结束后，数组应该呈现出一个特征：所有可归位的数字，都已经在自己的正确位置上。接下来，从头扫描：

• 对每一个下标i，判断nums[i] == i+1是否成立。
• 如果某个位置不成立，说明数字i+1缺失，直接返回i+1。
• 如果全部位置都成立，说明 1 到 n 全部出现过，返回n+1。

还是上面的例子，第一轮后数组[1, 2, 3, 4, 0]：

• i=0，nums[0]=1 == 1，通过。
• i=1，nums[1]=2 == 2，通过。
• i=2，nums[2]=3 == 3，通过。
• i=3，nums[3]=4 == 4，通过。
• i=4，nums[4]=0 != 5，返回5。

这里返回 5，而实际缺失的最小正整数确实是 5。

为什么“第一个不匹配的位置”就是答案？因为我们的映射规则是：下标 0 对应数字 1，下标 1 对应数字 2，以此类推。下标越靠前，对应的数字越小。第一次出现“该对上的没对上”，就说明最小的缺失正整数出现了。

3.3 完整代码实现（Python / Java / Go）

代码不长，但把细节写对很关键。下面给出三个常用语言的完整实现。

Python 版本：

def firstMissingPositive(nums): n = len(nums) i = 0 while i < n: v = nums[i] if 1 <= v <= n and nums[v - 1] != v: nums[i], nums[v - 1] = nums[v - 1], nums[i] else: i += 1 for i in range(n): if nums[i] != i + 1: return i + 1 return n + 1

Java 版本：

public int firstMissingPositive(int[] nums) { int n = nums.length; int i = 0; while (i < n) { int v = nums[i]; if (v >= 1 && v <= n && nums[v - 1] != v) { int tmp = nums[v - 1]; nums[v - 1] = nums[i]; nums[i] = tmp; } else { i++; } } for (int k = 0; k < n; k++) { if (nums[k] != k + 1) { return k + 1; } } return n + 1; }

Go 版本：

func firstMissingPositive(nums []int) int { n := len(nums) i := 0 for i < n { v := nums[i] if v >= 1 && v <= n && nums[v-1] != v { nums[i], nums[v-1] = nums[v-1], nums[i] } else { i++ } } for i := 0; i < n; i++ { if nums[i] != i+1 { return i + 1 } } return n + 1 }

看看，这里面的核心判断条件就是nums[v-1] != v，而不是v != i+1。为什么要用目标位置的值来判断？因为我们要避免重复元素引发的死循环，下一节会专门讲这个坑。

4. 正确性的直觉与严谨证明

4.1 交换操作为什么不会破坏已有结果

很多人第一次看到这个算法时会担心：我辛辛苦苦把数字 3 放到了下标 2 的位置，结果后面又一通交换，会不会把已经放好的 3 又给交换走了？

答案是不会。关键在于我们交换前的条件判断：只有当nums[v-1] != v时才交换。也就是说，如果数字v已经在它正确的位置上，我们根本不会拿它去交换。已经归位的数字，永远不会作为“被交换出去”的源。

那它会不会作为“被换进来”的目标呢？比如数字 3 已经在正确位置nums[2]=3，这时另一个位置上的某个数也想交换到下标 2。但我们的条件会检查nums[2]是否等于那个数，如果那个数也是 3，那么nums[2] == v，不交换；如果那个数不是 3，它要交换的目标是它自己对应的位置，而不是 3 的位置。因为每个数字v只交换到v-1这一个位置，所以不会把已经正确的 3 撞走。

更严谨地说，每次交换，都会把一个“不在正确位置”的数字放到正确位置，这个数字从此不会再被移动。因此交换总次数不会超过需要归位的数字个数，最多是 n 次。算法必然终止，而且不会破坏已经完成的结果。

4.2 为什么最后答案一定在 [1, n+1] 之间

这个结论虽然简单，但很重要。设数组长度为 n，那么数组里最多只能容纳 n 个不同的数字。如果我们从 1 开始数：

• 如果 1 到 n 全部出现在数组中，那么 n+1 就是缺失的最小正整数。
• 如果 1 到 n 中有缺失，那么第一个缺失的数字 k 一定在 1 到 n 之间。

不管哪种情况，答案都落在[1, n+1]范围内。这就是为什么我们在第一轮只处理[1, n]范围内的数字，因为超出这个范围的值不可能成为答案，也不必占据正确位置。

举个例子，如果数组是[7,8,9,11,12]，n=5，这些值全部大于 n，第一轮不用做任何交换。第二轮扫描时，nums[0]=7 != 1，直接返回 1。事实也确实如此：1 是缺失的最小正整数。

4.3 复杂度分析：时间真的 O(n) 吗

有人会质疑：第一轮里用了while循环，如果每次交换后都要继续处理，最坏情况下会不会导致 O(n²)？

不会。我们需要分析交换的总次数。每次交换，都会把一个数送到它的正确位置。当这个数到达正确位置后，它在后续交换中永远不会再被移动（上面已经论证）。因此，整个第一轮过程中，交换发生的总次数最多等于“需要归位的元素个数”，也就是不超过 n。

其余情况下，i都会增加 1，所以第一轮中“i++”的次数也是 n 次。因此第一轮总的操作次数是 O(n)。第二轮是简单的线性扫描，也是 O(n)。整体时间复杂度 O(n)，额外空间只用了一个临时交换变量，O(1)。

这里可以对比一下排序方案：排序 O(n log n) + 扫描 O(n)，总体 O(n log n)，时间上输给了原地哈希的 O(n)。正是在大 n 场景下，O(n) 和 O(n log n) 的差距会非常明显。

5. 动手实验：边界测试与典型坑位

5.1 一组容易翻车的测试用例

写代码的时候，边界测试是必不可少的。我整理了一份比较全面的用例清单，你可以拿去直接跑：

每一个用例都可以手动模拟一遍。我强烈建议你带着这些用例去跑自己的实现，很多时候你以为代码没问题，一跑边界就暴露了。

5.2 死循环是怎么产生的

这是新手最容易踩的坑，而且一踩一个准。很多人一开始会写出这样的代码：

# 错误示范 for i in range(n): if 1 <= nums[i] <= n and nums[i] != i + 1: nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

这个写法有两个问题：

问题一：用for循环，交换后没有继续处理当前位置的新值。比如nums[0]从 3 换来了 2，2 也需要归位，但for已经进入i=1，i=0位置留下了 2，最终扫描时才发现不对。

问题二：重复元素会引发无限循环。假设数组是[1,1]，i=0位置已经是正确的 1，继续处理没问题。但如果是[2,2]，i=0位置的v=2，目标位置nums[1]=2，此时如果不加nums[v-1] != v的判断，交换后nums[0]还是 2，nums[1]还是 2，数组没有任何变化，然后死循环。

正确的做法必须是：用while i < n作为外层循环，而且交换条件里必须有nums[v-1] != v。如果目标位置上已经有相同的值，说明这个值重复了，当前这个副本不需要再归位，直接跳过。

5.3 负数、零、重复数字的处理细节

负数、零这类数字，因为不在[1,n]区间内，直接跳过，不参与交换。它们会留在原处。但别担心，它们的存在不会影响最终答案，因为第二轮扫描时，我们看的是“位置和值是否匹配”，而不是看“数字是否出现在某个集合中”。

举个例子，数组[0,2,2,1,1]，n=5。第一轮：

• i=0，值 0 跳过。
• i=1，值 2，目标下标 1，nums[1]=2，等于当前值，跳过。
• i=2，值 2，目标下标 1，nums[1]=2，跳过。
• i=3，值 1，目标下标 0，nums[0]=0 != 1，交换，得到[1,2,2,0,1]。
• 回到i=3，当前值 0，跳过，i=4。
• i=4，值 1，目标下标 0，nums[0]=1，跳过，i=5。

第一轮结束数组[1,2,2,0,1]。第二轮扫描：i=0匹配；i=1匹配；i=2值为 2，不等于 3，返回 3。实际缺失的最小正整数确实是 3。

这个例子充分说明：重复数字虽然会导致某些正确位置被“占用”，但扫描时遇到同一个值占错了位置，依然能准确识别出空缺。

6. 从一道题到一类题：循环排序的套路化应用

6.1 循环排序的通用模板

刷题刷多了你会发现，“原地哈希”其实只是“循环排序（Cyclic Sort）”思想的一个典型应用。循环排序解决的是这么一类问题：给定一个长度为 n 的数组，数组元素都在某个明确的范围内（比如 1 到 n），要求原地把每个元素放到它对应的下标位置，空间复杂度 O(1)。

通用模板是这样的：

def cyclic_sort(nums): i = 0 n = len(nums) while i < n: v = nums[i] # 如果 v 在 [1, n] 范围内，并且不在正确位置，就交换 if 1 <= v <= n and nums[v - 1] != v: nums[i], nums[v - 1] = nums[v - 1], nums[i] else: i += 1

当题目出现以下特征时，可以优先考虑这个套路：

• 数组长度在代码中记为 n。
• 数组元素的值域是明确的，通常包含 1 到 n 中的一些数。
• 题目要求找出缺失、重复、多余的数字。
• 有严格的 O(1) 空间要求。

一旦识别出这些特征，你几乎可以立刻套模板，而不是从头开始想。

6.2 变体1：找回所有缺失的数字

有一道很经典的变形题：给定一个长度为 n 的数组，元素都是 1 到 n 范围内的整数，但有些元素重复出现，导致有些数字缺失。要求找出所有缺失的数字。

第一步，同样用循环排序把每个数字归位。排序结束后，数组会变成类似[1,2,3,3,5]这种形态。第二步，遍历数组，凡是nums[i] != i+1的位置，就把i+1收集到结果列表里。

以[2,3,2,1]为例，n=4。循环排序后得到[1,2,2,3]。扫描：i=0匹配，i=1匹配，i=2值 2 不等于 3，所以缺失数字是 3；i=3值 3 不等于 4，所以缺失数字是 4。最终答案是[3,4]。这道题的时间复杂度 O(n)，空间 O(1)，解法思路和本文主题一脉相承。

6.3 变体2：找重复数 / 找未排序数组中缺失的最小正数

还有一种变体是：给定范围 1 到 n 的数组，只含一个重复数字和一个缺失数字，要求找出重复和缺失。最简单的方法是用求和或异或，但循环排序同样能解决。

做法很简单：第一轮归位后，遍历数组，找到nums[i] != i+1的位置，那么：

• nums[i]就是重复的数字。
• i+1就是缺失的数字。

因为循环排序后，每个数字都应该在正确位置，如果某个位置上的值不是对应的下标加 1，说明这个位置被重复的那个数占着，而这个位置本该放的那个数就缺失了。

而“寻找缺失的第一个正数”本身，就是这类问题中最完整、最严格的一个版本。它允许负数、零、大于 n 的数出现，所以需要过滤无效值。可以说，只要把循环排序思想吃透，这些变体完全是一通百通。

6.4 面试中怎么展示思路

在面试场景中，遇到“寻找缺失的第一个正数”这类题，建议按下面的节奏表达：

1. 先讲朴素方案：排序 + 扫描，时间复杂度 O(n log n)；或者哈希集合，空间 O(n)。让面试官看到你有基础认知。
2. 再引出优化：因为答案范围在[1, n+1]，而且要求 O(1) 空间，所以可以用数组本身当哈希表。
3. 描述映射规则：数字k应该放在下标k-1，只处理[1,n]范围内的数。
4. 边写边解释关键点：为什么要用 while 而不是 for？为什么要判断nums[v-1] != v？这一步能体现你的代码细节掌控力。

面试官问的往往不是“你会不会做这道题”，而是“你能不能把思路讲清楚，并且把边界处理干净”。原地哈希这道题，就是一个很好的试金石。

最后再分享一个我自己的体会：我最初写这道题的时候，也踩过死循环的坑，当时盯着屏幕看了很久才意识到是重复元素导致的。后来我把循环排序的模板记下来，遇到类似的“数组 + O(1) 空间 + 找缺失/重复”的题目，直接套模板，正确率明显提高了。建议你也做一件事：把这一类题整理到同一个笔记里，对比它们的异同，比单纯刷题数量有效得多。