【LeetCode Hot 100】 - 缺失的第一个正数完全题解

题目描述给你一个未排序的整数数组nums请你找出其中没有出现的最小的正整数。请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。示例 1text输入nums [1,2,0] 输出3 解释1 和 2 都在数组中最小的缺失正数是 3示例 2text输入nums [3,4,-1,1] 输出2 解释1 在数组中2 缺失示例 3text输入nums [7,8,9,11,12] 输出1 解释1 不在数组中示例 4text输入nums [1] 输出2示例 5text输入nums [1,2,3,4,5] 输出6解题思路核心思想对于一个长度为n的数组缺失的第一个正数一定在[1, n1]范围内。证明如果数组包含了1到n的所有正整数那么答案就是n1否则答案就是[1, n]中缺失的那个数因此我们只需要关注1到n范围内的数字将它们放到正确的位置上。方法一哈希表不满足空间要求思路将所有数字存入哈希表然后从 1 开始递增查找。代码实现javapublic int firstMissingPositive(int[] nums) { SetInteger set new HashSet(); for (int num : nums) { set.add(num); } int missing 1; while (set.contains(missing)) { missing; } return missing; }复杂度分析时间复杂度O(n) — 一次遍历 最多 n 次查找空间复杂度O(n) — 哈希表存储所有元素优缺点✅ 思路简单直观❌ 空间复杂度 O(n)不满足题目常数空间要求方法二排序不满足时间要求思路排序后跳过负数和零然后找第一个缺失的正数。代码实现javapublic int firstMissingPositive(int[] nums) { Arrays.sort(nums); int missing 1; for (int num : nums) { if (num missing) { missing; } else if (num missing) { break; } } return missing; }复杂度分析时间复杂度O(n log n) — 排序空间复杂度O(log n) — 排序所需空间或 O(1) 如果原地排序优缺点✅ 代码简单❌ 时间复杂度 O(n log n)不满足题目 O(n) 要求方法三原地哈希最优解⭐核心思想利用数组索引作为哈希表将数字x放到索引x-1的位置上。规则只处理1到n范围内的数字将nums[i]放到nums[nums[i] - 1]的位置最终如果nums[i] ! i 1则i1就是缺失的第一个正数算法步骤遍历数组对于每个元素nums[i]如果1 nums[i] n且nums[i]不在正确位置上就交换交换后继续检查新换过来的数字再次遍历找到第一个nums[i] ! i 1的位置如果都正确返回n 1代码实现javapublic int firstMissingPositive(int[] nums) { int n nums.length; // 第一步将数字放到正确的位置 for (int i 0; i n; i) { // 循环交换直到 nums[i] 不在 [1, n] 范围内或者已经在正确位置 while (nums[i] 0 nums[i] n nums[nums[i] - 1] ! nums[i]) { swap(nums, i, nums[i] - 1); } } // 第二步找到第一个位置不对的数字 for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } // 第三步如果都在正确位置返回 n1 return n 1; } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; }手动模拟以nums [3, 4, -1, 1]为例n4第一步原地交换inums 数组操作0[3,4,-1,1]nums[0]3范围1-4目标位置2交换 nums[0] 和 nums[2] → [ -1,4,3,1 ]0[-1,4,3,1]nums[0]-1不在范围跳过1[-1,4,3,1]nums[1]4目标位置3交换 nums[1] 和 nums[3] → [ -1,1,3,4 ]1[-1,1,3,4]nums[1]1目标位置0交换 nums[1] 和 nums[0] → [ 1,-1,3,4 ]1[1,-1,3,4]nums[1]-1不在范围跳过2[1,-1,3,4]nums[2]3目标位置2已经在正确位置3[1,-1,3,4]nums[3]4目标位置3已经在正确位置最终数组[1, -1, 3, 4]第二步查找缺失正数索引 i期望值 i1实际值 nums[i]是否匹配011✅12-1❌ 返回 2结果2✅另一种写法标记法思路先将所有负数和零改为n1占位符遍历数组将|nums[i]|对应位置的数字标记为负数遍历数组第一个正数的位置就是答案代码实现javapublic int firstMissingPositive(int[] nums) { int n nums.length; // 第一步将所有负数、0 改为 n1这些数字不影响结果 for (int i 0; i n; i) { if (nums[i] 0) { nums[i] n 1; } } // 第二步使用索引作为哈希表标记出现过的正数 for (int i 0; i n; i) { int num Math.abs(nums[i]); if (num n) { // 将 num-1 位置的数字标记为负数 if (nums[num - 1] 0) { nums[num - 1] -nums[num - 1]; } } } // 第三步找到第一个正数的位置 for (int i 0; i n; i) { if (nums[i] 0) { return i 1; } } // 如果全部被标记返回 n1 return n 1; }手动模拟标记法nums [3, 4, -1, 1]n4第一步处理负数和零text[3, 4, -1, 1] → [-1 ≤ 0? 改为5] → [3, 4, 5, 1]第二步标记出现过的数字num3标记位置2[3, 4, 5, 1]→[3, 4, -5, 1]num4标记位置3[3, 4, -5, 1]→[3, 4, -5, -1]num5跳过5 4num1标记位置0[3, 4, -5, -1]→[-3, 4, -5, -1]第三步找第一个正数i0nums[0] -3 0i1nums[1] 4 0 → 返回 i1 2 ✅复杂度分析两种写法时间复杂度O(n) — 最多三次线性扫描空间复杂度O(1) — 原地修改数组优缺点✅ 时间复杂度 O(n)✅ 空间复杂度 O(1)✅ 满足题目要求⭐ 面试推荐写法方法四置换法带边界优化思路与方法三相同但增加了条件判断避免无效交换。代码实现javapublic int firstMissingPositive(int[] nums) { int n nums.length; for (int i 0; i n; i) { // 只有当 nums[i] 在 [1, n] 范围内且不在正确位置时才交换 while (nums[i] 1 nums[i] n nums[i] ! nums[nums[i] - 1]) { int targetIndex nums[i] - 1; // 交换 int temp nums[i]; nums[i] nums[targetIndex]; nums[targetIndex] temp; } } for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } return n 1; }方法对比总结方法时间复杂度空间复杂度是否满足题目要求推荐度哈希表O(n)O(n)❌ 空间不满足⭐⭐排序O(n log n)O(log n)❌ 时间不满足⭐⭐原地哈希交换法O(n)O(1)✅ 完美满足⭐⭐⭐⭐⭐原地哈希标记法O(n)O(1)✅ 完美满足⭐⭐⭐⭐图文详解以交换法为例核心思想图解text目标将数字放到正确的位置 数字 x 应该放在索引 x-1 的位置 数组索引: 0 1 2 3 4 5 正确数字: 1 2 3 4 5 6交换过程可视化text初始数组: [3, 4, -1, 1] (n4) 步骤1: i0, nums[0]3 3 应该去索引 2 交换 nums[0] 和 nums[2] [ -1, 4, 3, 1 ] 步骤2: i0, nums[0]-1 (不在1-4范围跳过) i1, nums[1]4 4 应该去索引 3 交换 nums[1] 和 nums[3] [ -1, 1, 3, 4 ] 步骤3: i1, nums[1]1 1 应该去索引 0 交换 nums[1] 和 nums[0] [ 1, -1, 3, 4 ] 步骤4: i1, nums[1]-1 (跳过) i2, nums[2]3 (已在正确位置) i3, nums[3]4 (已在正确位置) 最终数组: [1, -1, 3, 4] 检查: 索引0: 期望1 → 实际1 ✅ 索引1: 期望2 → 实际-1 ❌ 返回2为什么时间复杂度是 O(n)虽然使用了while循环但每个数字最多被交换一次一旦放到正确位置就不会再移动。总交换次数 ≤ n因此整体是 O(n)。常见问题 QAQ1为什么要限制范围在 1 到 nA因为答案只可能在这个范围内。如果[1, n]都出现了答案就是n1。超过n的数字我们可以忽略。Q2交换法中的 while 循环会不会导致死循环A不会。每次交换都会把一个数字放到正确位置正确位置的数字不会再被移动。最多交换 n 次后循环结束。Q3标记法中为什么要用绝对值A因为标记过程中可能把某个位置变成了负数取绝对值可以获取原始数值。Q4两种原地哈希方法哪个更好A交换法更直观更容易理解推荐面试使用标记法需要两次遍历代码稍复杂但思想也很巧妙Q5如何处理数组中已有的重复数字A交换时会自动处理。当遇到重复时nums[nums[i] - 1] ! nums[i]条件为 false不会交换避免了死循环。边界情况处理输入输出说明[]1空数组第一个正数是1[0]1只有01缺失[-1, -2, -3]1全是负数1缺失[1]2有1缺失2[1, 2, 3, 4, 5]61-5都在返回6[1, 1, 1, 1]2重复数字缺失2易错点总结交换条件写错必须是nums[nums[i] - 1] ! nums[i]否则会无限交换忘记处理重复数字重复数字会导致死循环索引越界交换前必须检查nums[i]在[1, n]范围内使用 while 而非 if因为交换后新数字可能还需要处理标记法忘记取绝对值标记后数字变负数需要取绝对值判断总结缺失的第一个正数是 LeetCode Hot 100 中一道考察原地算法和数组索引映射的经典题目。面试建议先分析答案范围在[1, n1]给出哈希表解法虽然不满足空间要求但展示思路最后给出原地哈希的交换法展示深度理解解释为什么时间复杂度是 O(n)核心要点理解答案范围限制[1, n1]掌握利用数组索引作为哈希表的技巧理解原地交换的原理能够处理边界情况负数、零、重复、空数组关键公式数字x的正确位置x-1位置i的正确数字i1参考链接LeetCode 41. 缺失的第一个正数 题目链接LeetCode 41. 缺失的第一个正数 官方题解