前言LeetCode 41 题「首个缺失的正数」First Missing Positive给定一个未排序的整数数组要求找出其中没有出现的最小正整数。难点在附加条件时间复杂度 O(n)额外空间 O(1)。如果允许额外空间做法很直接把所有正数放进哈希表再从 1 开始逐个查。但 O(1) 空间堵死了这条路逼着我们把数组本身当成哈希表用。常见误解有两个。第一以为要先排序——排序是 O(n log n)不满足要求。第二以为答案可能很大——长度为 n 的数组最多容纳 n 个正整数所以答案一定在1..n1之间。这个范围观察是整道题的钥匙大于 n 的数、零、负数都不可能是答案可以直接忽略。本文讲「原地哈希」的做法包括循环不变量、重复元素导致的死循环如何避免、以及复杂度为什么是 O(n) 而不是 O(n²)。代码以 C17 编写未在本机编译执行。一、关键观察答案的范围设数组长度为 n。如果数组恰好包含1, 2, ..., n这 n 个正整数那么首个缺失的正数是n1否则答案一定落在1..n之间。原因是要让1..k全部出现至少需要 k 个位置数组只有 n 个位置所以不可能让1..n1全部出现。因此小于等于 0 的数不可能是答案忽略。大于 n 的数不可能是答案忽略。位于1..n的数x它「应该」放在下标x-1的位置。这就把问题转化成一个放置问题把每个在范围内的数放到它对应的下标上然后从左到右检查「下标 i 上的数是不是 i1」第一个不满足的位置就是答案。二、原地哈希把数组当下标表// 适用于 C17#include utility#include vectorint firstMissingPositive(std::vectorint nums) {const int n static_castint(nums.size());for (int i 0; i n; i) {// 只要 nums[i] 在 [1, n] 内且它还没被放到正确位置就交换while (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) {std::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;}第一个循环是核心。对每个位置 i如果nums[i]是一个在1..n范围内的值v就把它换到下标v-1。交换后新到位置 i 的值可能仍然需要归位所以用while而不是if。第二个循环检查「下标 i 上是否是 i1」。第一个不满足的位置 i答案就是i1。如果全部满足说明1..n都出现了答案是n1。n 0时第一个循环不执行第二个循环不执行返回1正确。三、为什么不会死循环为什么是 O(n)while的条件里有一个容易被忽略的细节nums[nums[i] - 1] ! nums[i]。如果没有这个条件只有nums[i] 0 nums[i] n那么当数组里有重复值时会发生什么例如nums {1, 1}i0nums[0]1目标下标 0nums[0]已经是 1交换自己条件仍成立无限循环。加上「目标位置上的值不等于当前值」这个条件后nums[0] nums[0]为假循环终止。重复值不会被反复交换正确性也不受影响位置 1 上最终不是 2第二个循环会返回 2。复杂度分析每次交换都会把至少一个元素放到它的「最终位置」值v放到下标v-1而且已经到位的元素不会被换走因为条件要求目标位置的值不等于它。数组只有 n 个元素所以交换总次数不超过 n 次。外层循环执行 n 次内层while的总迭代次数摊还到 O(n)。第二个循环 O(n)。因此总时间复杂度 O(n)额外空间只有几个下标变量O(1)。「已经到位的元素不会被换走」可以严格说明每次交换把值v放到下标v-1。此后若某个位置 j 上的值也是v它的目标下标同样是v-1而那里已经是v条件nums[v-1] ! nums[j]为假不会发生交换。也就是说一个值一旦落到正确下标就不会再被移走每个值最多被放置一次交换总次数不超过 n。四、推演与其它写法以nums {3, 4, -1, 1}为例n 4步骤数组状态说明初始3 4 -1 1i0-1 4 3 13 与下标 2 的 -1 交换i0 继续-1 4 3 1-1 不在范围停止i1-1 1 3 44 与下标 3 的 1 交换i1 继续1 -1 3 41 与下标 0 的 -1 交换i1 继续1 -1 3 4-1 停止i21 -1 3 43 已在正确位置i31 -1 3 44 已在正确位置检查下标 1 是 -1 ≠ 2返回 2最终答案是 2符合预期。注意 i0 时交换后nums[0]变成 -1while条件立即为假不会继续。再看nums {7, 8, 9, 11, 12}n 5。所有值都大于 n第一个循环一次也不执行。第二个循环在下标 0 发现7 ! 1返回 1。正确。其它写法与取舍标记法把在1..n范围内的值v对应的下标v-1上的数改成负数表示「v 出现过」。最后找第一个非负位置。这种方法需要先把非正数和大于 n 的数替换成 1并单独检查 1 是否存在步骤更多且修改了符号信息。// 适用于 C17#include vectorint first_missing_positive_mark(std::vectorint nums) {const int n static_castint(nums.size());bool has_one false;for (int x : nums) {if (x 1) has_one true;if (x 0 || x n) x 1; // 无用值统一替换为 1}if (!has_one) return 1; // 替换可能伪造出 1需单独确认for (int x : nums) {int v x 0 ? -x : x;if (v 1 v n nums[v - 1] 0) {nums[v - 1] -nums[v - 1]; // 标记 v 出现过}}for (int i 0; i n; i) {if (nums[i] 0) return i 1; // 未被标记说明 i1 缺失}return n 1;}标记法的关键在has_one把越界值替换成 1 之后数组里一定「看起来有 1」如果不单独记录原始数组里是否真的有 1就会把答案 1 漏掉。另外标记时用的是绝对值因为前面的标记可能已经把某个位置改成了负数。这段代码比交换法长但每一步的意图更线性适合不习惯「边交换边归位」的读者。排序后扫描O(n log n)不满足题目要求但代码最短适合作为对拍用的暴力解。哈希集合O(n) 时间、O(n) 空间思路最直接适合在面试中先讲清楚再优化到 O(1) 空间。方法时间空间是否修改输入原地交换O(n)O(1)是标记负数O(n)O(1)是哈希集合O(n)O(n)否排序O(n log n)O(log n)排序栈是如果调用方不允许修改输入原地交换法需要先拷贝一份数组空间就变成 O(n)优势消失。这一点要在接口文档里写清楚。常见坑点❌ 内层用if而不是while交换一次就继续下一个下标。✅ 交换后新到当前位置的值可能仍需归位必须用while重复。❌while条件只写nums[i] 0 nums[i] n遇到重复值死循环。✅ 加上nums[nums[i] - 1] ! nums[i]目标位置已有相同值时停止。❌ 交换写成std::swap(nums[i], nums[nums[i]])下标差一。✅ 值v对应下标v - 1两处都要减一。❌ 最后返回i而不是i 1。✅ 下标 i 对应值 i1第一个不匹配处返回i1。❌ 循环结束后返回n。✅ 全部匹配说明1..n都在答案是n1。❌ 用int存nums.size()并假定不会溢出。✅ 题目规模下通常安全但工程代码应检查size()是否超过INT_MAX再转换。❌ 认为答案可能是 0 或负数。✅ 题目问的是正整数答案最小是 1。❌ 忘记函数会修改输入数组调用方后续还要用原数据。✅ 在文档中注明或先拷贝一份再处理。总结要点结论答案范围1..n1核心操作把值 v 换到下标 v-1循环条件范围内 目标位置值不同时间复杂度O(n)交换总次数不超过 n空间复杂度O(1)是否改输入是这道题的价值在于「用数组下标当哈希桶」这一转化当数据范围与数组长度同阶时值本身就可以作为下标从而省掉额外的哈希表。写对的关键只有两点——v-1的偏移以及重复值下while的终止条件。把这两点推演清楚代码就只有十来行却完整覆盖了空数组、全负数、全大于 n、含重复值等所有边界。