京公网安备11010502063487号给定一个未排序的整数数组，找出其中没有出现的最小的正整数，要求时间 O(n)、额外空间 O(1)。如果没有空间限制，用一个集合从 1 开始逐个查就行。要做到 O(1) 额外空间，需要把数组本身当作哈希表：长度为 n 的数组，答案一定落在 1 到 n + 1 之间，所以只关心 1 到 n 的数字，把数字 v 换到下标 v - 1 的位置，最后扫一遍，第一个"下标 i 处放的不是 i + 1"的位置，缺的就是 i + 1。本文用真实运行展示两种常见的写错方式，给出五种语言的实现，并把交换过程做成分步演示，最后如实报告这个 O(1) 空间的做法在 Python 里并不比集合法更快。
完整题目见官方页面（链接在文末）。基准解是集合法：把所有数放进集合，从 1 开始逐个查，找到第一个不在集合里的。一共 14 组用例，覆盖：官方示例、单个元素、全是负数、重复值、1 到 n 的乱序排列（答案是 n + 1）、超出数组长度的大数：
输入 [[1,2,0]] 输出 3 输入 [[3,4,-1,1]] 输出 2 输入 [[7,8,9,11,12]] 输出 1 输入 [[1]] 输出 2 输入 [[2]] 输出 1 输入 [[-1]] 输出 1
原地交换有两个容易写错的地方。第一，把数字 v 换到下标 v - 1 之前，要检查那个位置是不是已经是 v，否则遇到重复的值，或者数字本来就在正确位置时，会和自己交换、永远不结束。第二，处理下标 i 时要用 while 反复交换，直到 nums[i] 不能再交换为止，如果只用 if 交换一次，换过来的新数字就没有被处理。下面是两种错误写法与 solve 的真实结果（第一种写法我加了 1000 步的上限，超过就视为死循环）：
# 两种常见的错误写法 [1, 1]: 交换前不判断相等 -> 超过 1000 步仍未结束（死循环）；把 while 写成 if -> 2；solve -> 2 [3, 4, -1, 1]: 交换前不判断相等 -> 超过 1000 步仍未结束（死循环）；把 while 写成 if -> 1；solve -> 2 [2, 3, 4, 1]: 交换前不判断相等 -> 超过 1000 步仍未结束（死循环）；把 while 写成 if -> 1；solve -> 5 [4, 3, 2, 1]: 交换前不判断相等 -> 超过 1000 步仍未结束（死循环）；把 while 写成 if -> 5；solve -> 5
第一种写法在四组数据上全部死循环，包括 [4, 3, 2, 1] 这种没有重复的数组：只要某个数字已经在正确位置，它就会与自己交换，永远循环下去。第二种写法（if 代替 while）在 [1, 1] 上碰巧对了，在 [3, 4, -1, 1] 和 [2, 3, 4, 1] 上都答错（分别应该是 2 和 5，得到了 1）。
第一遍：对每个位置 i，只要 nums[i] 在 1 到 n 之间，并且 nums[nums[i] - 1] 不等于 nums[i]（目标位置上还不是它），就把它换过去。每一次交换都会让至少一个数字落到它的最终位置，所以总交换次数不超过 n，整体是 O(n)。第二遍：找第一个 nums[i] != i + 1 的位置，返回 i + 1；都对就返回 n + 1。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；这里的"原地"是修改输入数组本身。
Python · 解法代码def solve(nums): n = len(nums) for i in range(n): while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: # 数字 v 应该放在下标 v-1 的位置：把它换过去 j = nums[i] - 1 nums[i], nums[j] = nums[j], nums[i] for i in range(n): if nums[i] != i + 1: # 第一个"下标 i 放的不是 i+1"的位置，缺的就是 i+1 return i + 1 return n + 1 # 1..n 全在，缺的是 n+1
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,2,0]] → 3 [[3,4,-1,1]] → 2 [[7,8,9,11,12]] → 1 [[1]] → 2 [[2]] → 1 [[-1]] → 1
Java · 解法代码class Solution { public int firstMissingPositive(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { // 数字 v 应该放在下标 v-1：换过去 int j = nums[i] - 1; int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } } for (int i = 0; i < n; i++) { if (nums[i] != i + 1) return i + 1; // 第一个"下标 i 放的不是 i+1"的位置，缺的就是 i+1 } return n + 1; // 1..n 全在，缺的是 n+1 } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,2,0]] → 3 [[3,4,-1,1]] → 2 [[7,8,9,11,12]] → 1 [[1]] → 2 [[2]] → 1 [[-1]] → 1
Go · 解法代码func firstMissingPositive(nums []int) int { n := len(nums) for i := 0; i < n; i++ { for nums[i] >= 1 && nums[i] <= n && nums[nums[i]-1] != nums[i] { // 数字 v 应该放在下标 v-1：换过去 j := nums[i] - 1 nums[i], nums[j] = nums[j], nums[i] } } for i := 0; i < n; i++ { if nums[i] != i+1 { // 第一个"下标 i 放的不是 i+1"的位置，缺的就是 i+1 return i + 1 } } return n + 1 // 1..n 全在，缺的是 n+1 }
$ go build -o bin . && ./bin < cases.jsonl [[1,2,0]] → 3 [[3,4,-1,1]] → 2 [[7,8,9,11,12]] → 1 [[1]] → 2 [[2]] → 1 [[-1]] → 1
JavaScript · 解法代码function firstMissingPositive(nums) { const n = nums.length; for (let i = 0; i < n; i++) { while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) { // 数字 v 应该放在下标 v-1：换过去 const j = nums[i] - 1; [nums[i], nums[j]] = [nums[j], nums[i]]; } } for (let i = 0; i < n; i++) { if (nums[i] !== i + 1) return i + 1; // 第一个"下标 i 放的不是 i+1"的位置，缺的就是 i+1 } return n + 1; // 1..n 全在，缺的是 n+1 }
$ node run.js < cases.jsonl [[1,2,0]] → 3 [[3,4,-1,1]] → 2 [[7,8,9,11,12]] → 1 [[1]] → 2 [[2]] → 1 [[-1]] → 1
C++ · 解法代码#include <utility> #include <vector> using namespace std; class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; i++) { while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { // 数字 v 应该放在下标 v-1：换过去 swap(nums[i], nums[nums[i] - 1]); } } for (int i = 0; i < n; i++) { if (nums[i] != i + 1) return i + 1; // 第一个"下标 i 放的不是 i+1"的位置，缺的就是 i+1 } return n + 1; // 1..n 全在，缺的是 n+1 } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,2,0]] → 3 [[3,4,-1,1]] → 2 [[7,8,9,11,12]] → 1 [[1]] → 2 [[2]] → 1 [[-1]] → 1
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
数组是 1 到 n 的乱序排列（步长 7919 的伪随机排列，答案是 n + 1），这是需要交换最多的情形。每个规模取三次中最快的一次：
数组长度 n（1..n 的乱序排列，答案是 n+1） | 暴力解 | 本文解法
10007 | 0.447 ms | 1.293 ms
100003 | 6.501 ms | 13.921 ms
1000003 | 83.780 ms | 329.914 ms
3000017 | （未测，太慢） | 1209.695 ms必须如实说：在 Python 里，集合法（表里的"暴力解"）比原地交换更快，n = 100 万时是 83.8ms 对 329.9ms，约 4 倍。这个做法的价值在于空间：集合法需要额外 O(n) 的内存，原地交换只需要 O(1)。这里没有测量内存。原地交换的耗时从 10 万到 100 万（10 倍）增长约 23.7 倍，超过线性，我没有细究，可能与乱序访问的缓存行为有关，这只是猜测。
Python 版本另外和集合法做了随机对拍：
随机对拍 20000 组（长度 1 到 10、取值 -3 到 12 的随机数组（含负数、0、重复值、超过长度的大数）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [3, 4, -1, 1]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。i = 0 时，3 换到下标 2，换回来的是 -1，不在范围内；i = 1 时，4 换到下标 3，换回来的是 1，再换到下标 0；最后数组变成 [1, -1, 3, 4]，下标 1 处不是 2，缺失的就是 2。