本题采用原地哈希桶排序/基数排序思想算法解决“缺失的第一个正数”问题。其核心本质是利用数组的索引下标作为天然的哈希表键值通过不断的置换操作将符合范围的正整数强制归位到对应的物理位置。当前源码实现了在不占用额外内存空间的前提下进行数据的就位最终走向是通过第二次线性扫描首个未就位的元素索引来精确锁定目标缺失值。一、 问题本质与数据模型对于长度为 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二、 算法演进对比在解决动态正整数连续性判定问题时原地哈希置换法在时空资源的利用效率上达成了最优解解法名称时间复杂度空间复杂度核心原理物理缺陷 / 瓶颈标准双重循环排序O(n log n)O(1) 或 O(n)先对全数组进行快速排序或归并排序随后线性扫描查找断层时间开销受限于排序上限无法达到线性时间要求辅助哈希集合去重O(n)O(n)将所有数字存入 HashSet随后从 1 开始依次在集合中查询是否存在引入了与原数据等长的额外内存空间开销违反常数空间约束原地哈希置换当前解法O(n)O(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推进时的内部置换状态演进过程如下表所示步骤外层索引 i当前元素 nums[i]满足 while 条件与置换过程数组内部实时元素状态物理意义说明初始---[3, 4, -1, 1]原始无序状态103满足。目标索引j 3-1 2。与nums[2](-1) 互换。[-1, 4, 3, 1]数字 3 成功归位到下标 220-1-1 1不满足条件跳出 while。[-1, 4, 3, 1]当前位置为无效值指针右移314满足。目标索引j 4-1 3。与nums[3](1) 互换。[-1, 1, 3, 4]数字 4 成功归位到下标 3411满足。目标索引j 1-1 0。与nums[0](-1) 互换。[1, -1, 3, 4]数字 1 成功归位到下标 051-1-1 1不满足条件跳出 while。[1, -1, 3, 4]当前位置为无效值指针右移623nums[2] 21已正确就位跳过。[1, -1, 3, 4]指针右移734nums[3] 31已正确就位跳过。[1, -1, 3, 4]第一轮置换完全结束扫描从 0 到 3-检查到nums[1] -1 ! 2触发return i 1输出结果2五、源码实现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)。