第一次在刷题平台上看到“寻找缺失的第一个正数”这道题的时候我的第一反应是这不就是先排序再从头扫一遍的事吗但再一看题目的限制条件“原地修改数组只能使用常数级别额外空间”瞬间就没了底气。如果允许用哈希表这题甚至称不上中等难度但一旦加上原地这个约束它立刻变成了一道考察算法思维和边界控制能力的典型题目也就是标题里说的“原地哈希”。这道题的核心不是让你真的去实现一个哈希表而是让你意识到数组本身可以被改造成一张哈希表。下标就是键元素就是值利用交换把每个数字送回它该在的位置最后线性扫描就能拿到答案。整个过程不需要额外分配 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, n1]这个区间内。为什么因为如果 1 到 n 全都出现过那么 n1 就是缺失的最小正整数否则至少有一个 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, n1]而数组长度恰好是 n。这意味着一共只有 n 种可能的“答案候选值”。而我们刚好有一个长度为 n 的数组。那么问题来了能不能让数组的第 i 个位置去“代表”数字 i1 是否出现完全可以。我们可以定这样一个规则如果数组下标 i 上的值恰好等于 i1就说明数字 i1 存在于数组中。例如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下标超出数组长度放不下。这两类数字我们不管直接跳过。举个例子。假设n5数字 3 应该放在下标 2 处。而数字 6 呢它没有对应的位置因为数组长度只有 5我们只关心 1 到 5 是否齐全。如果 1 到 5 全部齐全答案就是 6也就是 n1。这就是整个映射关系的本质数组的每一个可用下标都对应一个“需要被检查是否存在的正整数”。2.3 哪些数可以直接忽略在交换归位的过程中我们只需要处理满足1 nums[i] n的数字。对于以下三种情况直接跳过负数比如 -2它不可能成为答案也不需要放进某个下标。零0 不是正整数跳过。大于 n 的正数比如 n5它不在我们的检查范围内因为答案最大也不可能超过 n1当 1 到 n 都齐全时答案就是 n1这个 n5 根本不会影响判断。但注意“跳过”不等于“删除”。交换过程中这些无关数字可能会被换到数组的各个位置但它们不会进入目标位置最终只会留在某些“错误位置”上。第二轮扫描时我们只要找到第一个nums[i] ! i1的位置就能判断出缺失的数字。这里再补充一个容易误解的点第一轮结束后数组中仍然可能存在负数、零、大于 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]i0v3合法目标下标2nums[2]4 ! 3交换得到[4, 1, 3, 2, 0]。此时i0位置的值变成 4v4合法目标下标3nums[3]2 ! 4交换得到[2, 1, 3, 4, 0]。继续检查i0当前值变成 2合法目标下标1nums[1]1 ! 2交换得到[1, 2, 3, 4, 0]。现在i0位置的值为 1已经在正确位置i。之后i1位置值为 2正确i2位置值为 3正确i3位置值为 4正确i4位置值为 0不在[1,n]跳过i变成 5循环结束。经过第一轮数组变成[1, 2, 3, 4, 0]。1 到 4 全部归位0 留在最后。3.2 第二轮扫描找出第一个“座位空着”的位置第一轮结束后数组应该呈现出一个特征所有可归位的数字都已经在自己的正确位置上。接下来从头扫描对每一个下标i判断nums[i] i1是否成立。如果某个位置不成立说明数字i1缺失直接返回i1。如果全部位置都成立说明 1 到 n 全部出现过返回n1。还是上面的例子第一轮后数组[1, 2, 3, 4, 0]i0nums[0]1 1通过。i1nums[1]2 2通过。i2nums[2]3 3通过。i3nums[3]4 4通过。i4nums[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 1Java 版本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] ! i1 { return i 1 } } return n 1 }看看这里面的核心判断条件就是nums[v-1] ! v而不是v ! i1。为什么要用目标位置的值来判断因为我们要避免重复元素引发的死循环下一节会专门讲这个坑。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, n1] 之间这个结论虽然简单但很重要。设数组长度为 n那么数组里最多只能容纳 n 个不同的数字。如果我们从 1 开始数如果 1 到 n 全部出现在数组中那么 n1 就是缺失的最小正整数。如果 1 到 n 中有缺失那么第一个缺失的数字 k 一定在 1 到 n 之间。不管哪种情况答案都落在[1, n1]范围内。这就是为什么我们在第一轮只处理[1, n]范围内的数字因为超出这个范围的值不可能成为答案也不必占据正确位置。举个例子如果数组是[7,8,9,11,12]n5这些值全部大于 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 一组容易翻车的测试用例写代码的时候边界测试是必不可少的。我整理了一份比较全面的用例清单你可以拿去直接跑输入数组期望输出说明[]1空数组最小正数缺失就是1[1]2只有一个元素且为1缺失的是2[1,2,0]3经典用例0属于干扰项[3,4,-1,1]2负数和越界数混合[7,8,9,11,12]1全是大于n的数答案是1[1,1]2重复元素且缺失2[2,2]1重复元素缺失1[1,2,3,4]51到n全部出现答案是n1[0,2,2,1,1]3重复元素 零 缺3每一个用例都可以手动模拟一遍。我强烈建议你带着这些用例去跑自己的实现很多时候你以为代码没问题一跑边界就暴露了。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 换来了 22 也需要归位但for已经进入i1i0位置留下了 2最终扫描时才发现不对。问题二重复元素会引发无限循环。假设数组是[1,1]i0位置已经是正确的 1继续处理没问题。但如果是[2,2]i0位置的v2目标位置nums[1]2此时如果不加nums[v-1] ! v的判断交换后nums[0]还是 2nums[1]还是 2数组没有任何变化然后死循环。正确的做法必须是用while i n作为外层循环而且交换条件里必须有nums[v-1] ! v。如果目标位置上已经有相同的值说明这个值重复了当前这个副本不需要再归位直接跳过。5.3 负数、零、重复数字的处理细节负数、零这类数字因为不在[1,n]区间内直接跳过不参与交换。它们会留在原处。但别担心它们的存在不会影响最终答案因为第二轮扫描时我们看的是“位置和值是否匹配”而不是看“数字是否出现在某个集合中”。举个例子数组[0,2,2,1,1]n5。第一轮i0值 0 跳过。i1值 2目标下标 1nums[1]2等于当前值跳过。i2值 2目标下标 1nums[1]2跳过。i3值 1目标下标 0nums[0]0 ! 1交换得到[1,2,2,0,1]。回到i3当前值 0跳过i4。i4值 1目标下标 0nums[0]1跳过i5。第一轮结束数组[1,2,2,0,1]。第二轮扫描i0匹配i1匹配i2值为 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] ! i1的位置就把i1收集到结果列表里。以[2,3,2,1]为例n4。循环排序后得到[1,2,2,3]。扫描i0匹配i1匹配i2值 2 不等于 3所以缺失数字是 3i3值 3 不等于 4所以缺失数字是 4。最终答案是[3,4]。这道题的时间复杂度 O(n)空间 O(1)解法思路和本文主题一脉相承。6.3 变体2找重复数 / 找未排序数组中缺失的最小正数还有一种变体是给定范围 1 到 n 的数组只含一个重复数字和一个缺失数字要求找出重复和缺失。最简单的方法是用求和或异或但循环排序同样能解决。做法很简单第一轮归位后遍历数组找到nums[i] ! i1的位置那么nums[i]就是重复的数字。i1就是缺失的数字。因为循环排序后每个数字都应该在正确位置如果某个位置上的值不是对应的下标加 1说明这个位置被重复的那个数占着而这个位置本该放的那个数就缺失了。而“寻找缺失的第一个正数”本身就是这类问题中最完整、最严格的一个版本。它允许负数、零、大于 n 的数出现所以需要过滤无效值。可以说只要把循环排序思想吃透这些变体完全是一通百通。6.4 面试中怎么展示思路在面试场景中遇到“寻找缺失的第一个正数”这类题建议按下面的节奏表达先讲朴素方案排序 扫描时间复杂度 O(n log n)或者哈希集合空间 O(n)。让面试官看到你有基础认知。再引出优化因为答案范围在[1, n1]而且要求 O(1) 空间所以可以用数组本身当哈希表。描述映射规则数字k应该放在下标k-1只处理[1,n]范围内的数。边写边解释关键点为什么要用 while 而不是 for为什么要判断nums[v-1] ! v这一步能体现你的代码细节掌控力。面试官问的往往不是“你会不会做这道题”而是“你能不能把思路讲清楚并且把边界处理干净”。原地哈希这道题就是一个很好的试金石。最后再分享一个我自己的体会我最初写这道题的时候也踩过死循环的坑当时盯着屏幕看了很久才意识到是重复元素导致的。后来我把循环排序的模板记下来遇到类似的“数组 O(1) 空间 找缺失/重复”的题目直接套模板正确率明显提高了。建议你也做一件事把这一类题整理到同一个笔记里对比它们的异同比单纯刷题数量有效得多。