《缺失的第一个正数：原地哈希算法的理论与实践》

摘要

缺失的第一个正数问题是数组处理领域的经典算法问题，要求在未排序整数数组中找出未出现的最小正整数，同时需满足时间复杂度 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 算法步骤

1. 原地置换：遍历数组，对于每个元素 nums[i]，若满足 1≤nums[i]≤n 且 nums[nums[i]−1]=nums[i]，则将 nums[i] 与 nums[nums[i]−1] 交换，直到当前位置元素不满足置换条件；
2. 查找缺失值：再次遍历数组，若 nums[i]=i+1，则返回 i+1；
3. 全匹配情况：若数组所有位置均满足 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. 与其他方法的对比

7. 结论与扩展

原地哈希法是解决 “缺失的第一个正数” 问题的最优解法，其通过 “值与索引的映射” 实现了原地排序，在严格满足 O(n) 时间与 O(1) 空间约束的同时，保证了算法的正确性与高效性。