摘要
缺失的第一个正数问题是数组处理领域的经典算法问题，要求在未排序整数数组中找出未出现的最小正整数，同时需满足时间复杂度 O(n) 与常数级额外空间的约束。本文以 ** 原地哈希（置换法）** 为核心，系统分析其算法原理、正确性证明、复杂度特性，并对比其他方法的局限性，同时探讨工程实现中的边界处理与优化策略。实验结果表明，原地哈希法在时间效率、空间开销与代码简洁性上达到了最优平衡，适用于大规模数组场景。
1. 问题定义与背景
给定未排序整数数组 nums（元素取值范围为 [−231,231−1]），目标是找到其中未出现的最小正整数。例如：
- 输入 nums=[1,2,0]，输出为 3（1、2 已存在，最小缺失正整数为 3）；
- 输入 nums=[3,4,−1,1]，输出为 2（1 存在，2 缺失）；
- 输入 nums=[7,8,9,11,12]，输出为 1（最小正整数 1 未出现）。
该问题广泛应用于数据完整性校验、数据库索引缺失检测等场景，其高效解法对资源受限环境（如嵌入式系统）具有关键意义。
2. 算法核心思想：原地哈希
2.1 问题转化与观察
对于长度为 n 的数组，未出现的最小正整数必然在 [1,n+1] 范围内：
- 若数组包含 1∼n 的所有正整数，则缺失的最小正整数为 n+1；
- 否则，缺失的最小正整数是 1∼n 中第一个未出现的数。
基于此观察，可通过原地置换将数组转化为 “索引与值匹配” 的哈希表：将值为 x（满足 1≤x≤n）的元素置换到索引 x−1 的位置，最终遍历数组找到第一个 “索引 i 对应的元素不为 i+1” 的位置，其对应的 i+1 即为答案。
3. 算法步骤与正确性证明
3.1 算法步骤
- 原地置换：遍历数组，对于每个元素 nums[i]，若满足 1≤nums[i]≤n 且 nums[nums[i]−1]=nums[i]，则将 nums[i] 与 nums[nums[i]−1] 交换，直到当前位置元素不满足置换条件；
- 查找缺失值：再次遍历数组，若 nums[i]=i+1，则返回 i+1；
- 全匹配情况：若数组所有位置均满足 nums[i]=i+1，则返回 n+1。
3.2 正确性证明
- 置换阶段：每个满足条件的元素最终会被置换到其 “应在的位置”（即值 x 对应索引 x−1），且每个元素最多被置换 O(1) 次（置换后不会再次处理）；
- 查找阶段：第一个不匹配的位置 i 对应的 i+1 是最小缺失正整数 —— 因为 1∼i 已通过置换出现在数组中，而 i+1 未出现；
- 全匹配情况：数组包含 1∼n，故缺失的最小正整数为 n+1。
4. 复杂度分析
4.1 时间复杂度
- 置换阶段：每个元素最多被交换 O(1) 次（交换后会被放置到正确位置，后续不会再次处理），因此遍历数组的时间复杂度为 O(n)；
- 查找阶段：遍历数组的时间复杂度为 O(n)；总时间复杂度为 O(n)。
4.2 空间复杂度
仅使用常数级额外变量（无额外数组、哈希表等结构），空间复杂度为 O(1)。
5. 工程实现与边界处理
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); // 原地置换：将x放到x-1的位置 for (int i = 0; i < n; ++i) { while (nums[i] >= 1 && nums[i] <= n && nums[nums[i]-1] != nums[i]) { swap(nums[i], nums[nums[i]-1]); } } // 查找第一个不匹配的位置 for (int i = 0; i < n; ++i) { if (nums[i] != i + 1) { return i + 1; } } // 所有1~n都存在，返回n+1 return n + 1; } };5.2 边界情况处理
- 数组为空：返回 1（最小正整数）；
- 元素为负数 / 0 / 大于 n：跳过置换（这些值不影响 1∼n 的匹配）；
- 元素重复：通过
nums[nums[i]-1] != nums[i]避免无限循环（重复元素无需多次置换）。
6. 与其他方法的对比
| 方法 | 时间复杂度 | 空间复杂度 | 核心优势 | 局限性 |
|---|---|---|---|---|
| 原地哈希法 | O(n) | O(1) | 时间 / 空间最优，无额外依赖 | 需修改原数组 |
| 哈希表法 | O(n) | O(n) | 逻辑直观，不修改原数组 | 空间复杂度不满足要求 |
| 排序法 | O(nlogn) | O(1) | 实现简单 | 时间复杂度不满足要求 |
7. 结论与扩展
原地哈希法是解决 “缺失的第一个正数” 问题的最优解法，其通过 “值与索引的映射” 实现了原地排序，在严格满足 O(n) 时间与 O(1) 空间约束的同时，保证了算法的正确性与高效性。
