hot100 缺失的第一个整数(41)

本题采用原地哈希（桶排序/基数排序思想）算法解决“缺失的第一个正数”问题。其核心本质是利用数组的索引下标作为天然的哈希表键值，通过不断的置换操作将符合范围的正整数强制归位到对应的物理位置。当前源码实现了在不占用额外内存空间的前提下进行数据的就位，最终走向是通过第二次线性扫描首个未就位的元素索引来精确锁定目标缺失值。

一、 问题本质与数据模型

对于长度为 n 的整数数组 nums，我们需要寻找没有出现的最小正整数。在处理该问题时，首先需要通过数学归纳确立结果的物理边界：

• 最理想情况：如果数组包含从 1 到 n 的所有正整数[1, 2, 3, ..., n]，那么缺失的第一个正整数必然为n + 1。

• 非理想情况：如果数组中存在小于等于 0 的数、大于 n 的数、或是重复的数，根据抽屉原理（鸽巢原理），缺失的第一个正整数必然落在[1, n]的有效闭区间内。

由此可得，最终的答案必然位于[1, n + 1]之间。

这一数学边界直接决定了我们的数据模型：我们完全不需要理会小于等于 0 或大于 n 的数字，只需要聚焦于满足1 <= nums[i] <= n范围内的正整数，并设法验证它们是否全部就位。

在不被允许开辟额外哈希表的前提下，算法将原数组自身视为一个哈希表。对于任意满足范围的数值x，它在哈希表中的标准归宿就是数组的x - 1下标位置。即算法最终的目标是让数组尽可能满足：

nums[i] == i + 1

二、 算法演进对比

在解决动态正整数连续性判定问题时，原地哈希置换法在时空资源的利用效率上达成了最优解：

三、 原地哈希置换的核心控制逻辑

当前源码的卓越性在于通过一个内嵌的while循环实现了无额外空间的“数据自动归位”。其核心判定条件由三部分组成：

while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])

1. 数值合法性过滤：nums[i] >= 1 && nums[i] <= n

只有当前元素位于[1, n]区间内时，它才拥有在数组中被归位的资格。任何负数、0 以及超出数组长度的大整数都无法匹配任何合法的数组下标，直接跳过。

2. 目标冲突判定：nums[nums[i] - 1] != nums[i]

这是防止算法陷入死循环的核心防护网。

• 设当前位置的数值为x = nums[i]，它本应该待的地方是目标索引j = x - 1。

• 只有当目标位置上的数值nums[j]还不等于x时（即nums[nums[i] - 1] != nums[i]），才需要执行交换。

• 逻辑证明：如果满足nums[j] == x，说明该数字在目标位置上已经存在（遇到了重复元素）。此时如果继续交换，当前位置的值不会发生改变，while循环将永远无法退出。

3. 为什么必须使用while而不是if？

当我们将nums[i]交换到它应该去的目的地nums[j]后，原本待在nums[j]的那个未知元素被换到了当前位置i。这个换过来的新元素同样可能是个合法的、需要归位的数字。因此必须使用while循环不断对当前位置i上的新元素进行重复判定与置换，直到换过来的元素是一个非法值或是一个已经正确就位的元素为止。

四、 算法执行状态机步进示例

以输入数据nums = [3, 4, -1, 1]为例（此时数组长度n = 4），外层循环变量i推进时的内部置换状态演进过程如下表所示：

五、源码实现

class Solution { public int firstMissingPositive(int[] nums) { // 边界安全检查 if (nums == null || nums.length == 0) { return 1; } int n = nums.length; // 步骤 1：原地哈希置换，尝试将每个满足 [1, n] 范围的数字 x 放到对应的下标 x - 1 上 for (int i = 0; i < n; i++) { // 使用 while 循环，持续对换到当前位置 i 的新元素进行就位处理 // 条件包含：数值在合法区间内，且目标位置上的数值与当前数值不相等（防重复死循环） while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { // 计算目标归宿索引 int j = nums[i] - 1; // 进行原地元素对调 int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } // 步骤 2：再次扫描调整后的数组，寻找第一个没有正确就位的物理位置 for (int i = 0; i < n; i++) { // 如果当前位置的值不等于 索引 + 1，说明该正整数缺失 if (nums[i] != i + 1) { return i + 1; } } // 步骤 3：如果数组中 [1, n] 的所有正整数都正确就位了，则缺失的必然是 n + 1 return n + 1; } }

六、 复杂度极限分析

1. 时间复杂度 O(n)

• 精确摊还分析：虽然代码的结构上表现为for循环内部嵌套了一个while循环，但我们不能简单地将其评估为平方阶。从物理置换的本质来看，每一次成功的swap操作，都必然会将至少一个原本错位的数字送入到它长久正确的最终位置（即满足nums[j] == j + 1）。

• 结论：一旦一个元素正确就位，它就绝不会再次被挪动。由于数组中总共只有 n 个元素，整个算法生命周期里发生的总交换次数绝对不会超过n - 1次。因此，while循环的平均摊还时间开销为常数阶 O(1)，结合随后的第二次线性扫描，综合总时间复杂度稳定在 O(n)。

2. 空间复杂度 O(1)

• 分析：算法所有的元素移位、调配与对调逻辑全部直接施加在传入的原始nums数组内存块上展开（原地算法）。执行期间，除独立声明了n,i,j,temp等有限个用于控制迭代和辅助对调的基础类型整型变量外，没有申请任何与输入规模相关的外部数据结构。

• 结论：额外内存的消耗固定为常数阶，空间复杂度为严格的 O(1)。