杭州市网站建设_网站建设公司_悬停效果_seo优化

Java版LeetCode热题100之“缺失的第一个正数”：O(n)时间与O(1)空间的极致挑战

摘要：本文深入剖析 LeetCode 第 41 题 “缺失的第一个正数”，全面覆盖原题回顾、算法构思、两种主流解法（标记法与置换法）、代码实现、复杂度分析、面试高频问答、实际应用场景及延伸思考。我们将从朴素思路出发，逐步演进至满足O(n) 时间 + O(1) 空间的最优解，并揭示其背后精妙的“原地哈希”思想，助你彻底掌握这一经典难题。

一、原题回顾

题目名称：缺失的第一个正数
题目编号：LeetCode 41
难度等级：困难（Hard）

题目描述

给你一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数。

要求：

• 实现时间复杂度为 O(n)
• 只使用常数级别额外空间

示例

示例 1： 输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。 示例 2： 输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。 示例 3： 输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。

约束条件

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1

二、原题分析

初步观察

• 数组未排序，且包含负数、零、重复数、超大正数
• 目标是找最小缺失的正整数，即从 1 开始向上找第一个不在数组中的数

关键洞察

对于长度为 N 的数组，答案一定在 [1, N+1] 范围内！

为什么？

• 最理想情况：数组恰好包含[1, 2, 3, ..., N]→ 缺失的是N+1
• 其他情况：至少有一个数在[1, N]中缺失 → 答案 ∈[1, N]

因此，我们只需关注 [1, N] 范围内的数，其他数（≤0 或 >N）可忽略或处理。

常见解法及其缺陷

题目要求O(n) 时间 + O(1) 空间，意味着我们必须利用原数组本身作为辅助存储！

这引出了本题的核心思想：原地哈希（In-place Hashing）

三、答案构思

核心思想：原地哈希

既然不能用额外空间建哈希表，那就把原数组当作哈希表用！

如何做？

• 哈希表的作用：快速判断“某个数是否存在”
• 我们希望：若数字x ∈ [1, N]存在，则在数组的某个位置打上“存在标记”

有两种主流实现方式：

方法一：标记法（利用符号位）

• 将数组中所有 ≤0 的数替换为N+1（使其无效化）
• 遍历数组，对每个x ∈ [1, N]，将nums[x-1]变为负数（打标记）
• 最后找第一个正数的位置 → 即为缺失的最小正整数

方法二：置换法（将数字放到正确位置）

• 遍历数组，若nums[i] ∈ [1, N]且不在正确位置（即nums[i] != i+1），则将其交换到nums[nums[i]-1]
• 重复此过程，直到无法交换
• 最终，若nums[i] != i+1，则i+1缺失

两种方法均满足 O(n) 时间、O(1) 空间，但实现细节和鲁棒性略有不同。

四、完整答案（Java 实现）

方法一：标记法（推荐，简洁稳定）

classSolution{publicintfirstMissingPositive(int[]nums){intn=nums.length;// 第一步：将所有非正数（<=0）替换为 n+1（使其无效）for(inti=0;i<n;i++){if(nums[i]<=0){nums[i]=n+1;}}// 第二步：遍历数组，对每个在 [1, n] 范围内的数 x，// 将 nums[x-1] 变为负数（打标记）for(inti=0;i<n;i++){intnum=Math.abs(nums[i]);// 取绝对值，防止已被标记为负if(num<=n){// 将对应位置的数变为负（注意避免重复取负）nums[num-1]=-Math.abs(nums[num-1]);}}// 第三步：找到第一个正数的位置，返回 index + 1for(inti=0;i<n;i++){if(nums[i]>0){returni+1;}}// 若全部为负，说明 [1, n] 都存在，返回 n+1returnn+1;}}

方法二：置换法（巧妙，但需防死循环）

classSolution{publicintfirstMissingPositive(int[]nums){intn=nums.length;// 将每个在 [1, n] 范围内的数放到其“正确位置”for(inti=0;i<n;i++){// 循环交换，直到 nums[i] 不在 [1, n] 或已在正确位置while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){// 交换 nums[i] 和 nums[nums[i] - 1]inttemp=nums[nums[i]-1];nums[nums[i]-1]=nums[i];nums[i]=temp;}}// 遍历检查：若 nums[i] != i+1，则 i+1 缺失for(inti=0;i<n;i++){if(nums[i]!=i+1){returni+1;}}returnn+1;}}

✅建议：面试时优先写方法一（逻辑清晰、不易出错），再提方法二作为优化或变体。

五、代码分析

方法一：标记法详解

步骤1：无效化非目标数

if(nums[i]<=0)nums[i]=n+1;

• 目的：确保后续只处理[1, n]的数
• 为何用n+1？因为n+1 > n，不会干扰[1, n]的标记

步骤2：打标记（关键！）

intnum=Math.abs(nums[i]);if(num<=n){nums[num-1]=-Math.abs(nums[num-1]);}

• 取绝对值：因为nums[i]可能已被前面的操作标记为负
• 再次取绝对值再取负：防止nums[num-1]已为负，重复取负变正（错误！）
  • 例如：若nums[0] = -3，直接nums[0] = -nums[0]会变成3，丢失标记

💡 这是最容易出错的地方！必须用-Math.abs(...)确保结果为负。

步骤3：找第一个未标记位置

• 正数表示该位置对应的数（index+1）未出现
• 全负 →[1, n]全出现 → 返回n+1

示例演示：nums = [3,4,-1,1]

1. 无效化：[-1 → 5]→[3,4,5,1]
2. 打标记：
   • i=0: num=3 → nums[2] = -5 →[3,4,-5,1]
   • i=1: num=4 → nums[3] = -1 →[3,4,-5,-1]
   • i=2: num=5（>4）→ 跳过
   • i=3: num=1 → nums[0] = -3 →[-3,4,-5,-1]
3. 找正数：nums[1] = 4 > 0→ 返回1+1 = 2✅

方法二：置换法详解

核心循环

while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){swap(nums[i],nums[nums[i]-1]);}

• 条件1 & 2：确保nums[i] ∈ [1, n]
• 条件3：防止死循环（当nums[i] == nums[nums[i]-1]时，已就位）

为何不会无限循环？

• 每次有效交换都会将一个数放到正确位置（即nums[x-1] = x）
• 一旦就位，下次遇到它就不会再交换
• 总共最多n次交换 → 时间 O(n)

示例演示：nums = [3,4,-1,1]

初始：[3,4,-1,1]

• i=0: nums[0]=3 → 应放位置2 → 交换 nums[0] 和 nums[2] →[-1,4,3,1]
  • 现在 nums[0]=-1（无效），i++
• i=1: nums[1]=4 → 应放位置3 → 交换 nums[1] 和 nums[3] →[-1,1,3,4]
  • 现在 nums[1]=1 → 应放位置0 → 交换 nums[1] 和 nums[0] →[1,-1,3,4]
  • 现在 nums[1]=-1（无效），i++
• i=2: nums[2]=3 → 已在位置2（3-1=2）→ 跳过
• i=3: nums[3]=4 → 已在位置3 → 跳过

最终：[1,-1,3,4]→ 检查：

• i=0: 1==1 ✅
• i=1: -1 != 2 → 返回 2 ✅

六、时间复杂度与空间复杂度分析

方法一：标记法

• 时间复杂度：O(n)
  • 三次独立遍历，每次 O(n)，总 O(3n) = O(n)
• 空间复杂度：O(1)
  • 仅使用常数个变量（如num）
  • 修改原数组，但题目未禁止（且是实现 O(1) 空间的必要手段）

方法二：置换法

• 时间复杂度：O(n)
  • 外层 for 循环 O(n)
  • 内层 while 循环：每个元素最多被交换一次到正确位置，总交换次数 ≤ n
  • 整体仍为 O(n)
• 空间复杂度：O(1)
  • 仅用常数额外变量（temp）

✅ 两种方法均严格满足题目要求。

七、常见问题解答（FAQ）

Q1：为什么答案一定在 [1, n+1]？

A：反证法。

• 假设答案 > n+1，即 [1, n+1] 都在数组中
• 但数组只有 n 个位置，不可能容纳 n+1 个不同的正整数
• 矛盾！故答案 ≤ n+1
• 又因正整数从 1 开始，故答案 ∈ [1, n+1]

Q2：方法一中为什么要用-Math.abs(...)而不是直接-nums[...]？

A：防止“负负得正”。

• 假设nums[2] = -5（已被标记）
• 若执行nums[2] = -nums[2]→ 变成5，标记丢失！
• 用-Math.abs(-5) = -5，保持负号，正确。

Q3：方法二中为何要检查nums[nums[i]-1] != nums[i]？

A：避免死循环。

• 例如nums = [1,1]
• i=0: nums[0]=1，应放位置0 →nums[1-1] = nums[0] = 1，相等
• 若不检查，会不断交换nums[0]和nums[0]，无限循环

Q4：如果数组中有重复数字怎么办？

A：两种方法都能正确处理。

• 标记法：重复数字多次打同一位置标记，无影响
• 置换法：重复数字在交换时会因“已在正确位置”而停止

Q5：能否不修改原数组？

A：不能同时满足 O(n) 时间和 O(1) 空间。

• 若不允许修改数组，则必须用额外空间记录状态（如位图、哈希表），空间至少 O(n)
• 本题的 O(1) 空间解法依赖于修改原数组

八、优化思路总结

工程建议：

• 优先选择标记法：逻辑线性，边界清晰，适合生产环境
• 置换法可作为面试中的“炫技”方案，展示对数组操作的熟练度

九、数据结构与算法基础知识点回顾

1. 原地哈希（In-place Hashing）

• 定义：利用输入数组本身的下标作为哈希地址，值作为存储内容
• 前提：问题的解空间有限（如本题 [1, n+1]）
• 实现方式：
  • 利用符号位（正/负）
  • 利用偏移量（加 n）
  • 利用置换（将值放到对应下标）

2. 数组索引与值的映射

• 本题建立映射：值 x ↔ 下标 x-1
• 这是处理“1-based 正整数”与“0-based 数组”的标准技巧

3. 边界条件处理

• 空数组：题目保证 n≥1，无需考虑
• 全负数：如[-1,-2]→ 答案=1
• 全大于n：如[5,6,7]（n=3）→ 答案=1
• 包含1~n：如[1,2,3]→ 答案=4

4. 时间复杂度的“摊还分析”

• 置换法的内层 while 看似嵌套，但每个元素最多被移动一次
• 总操作次数为 O(n)，属于摊还 O(1)每次操作

十、面试官提问环节（模拟对话）

Q：你的解法修改了原数组，如果面试官要求不能修改呢？

A：若不能修改原数组，则无法同时满足 O(n) 时间和 O(1) 空间。我会说明这一点，并给出两种妥协方案：

1. 允许 O(n) 空间：用 HashSet，O(n) 时间
2. 允许 O(n log n) 时间：先复制数组再排序，O(1) 额外空间（若不算复制）

Q：方法一中，如果数组里有 Integer.MAX_VALUE，替换为 n+1 会溢出吗？

A：不会。因为n <= 10^5，所以n+1 <= 100001，远小于Integer.MAX_VALUE (≈2e9)。即使n=10^5，n+1也安全。

Q：能否用位运算优化空间？

A：理论上可以用位图（Bitmap），用一个 int 表示 32 个数的存在性。但：

• 需要(n+31)/32个 int，空间仍是 O(n)
• 且题目要求 O(1) 空间，位图不符合
• 本题的 O(1) 解法必须依赖原数组

Q：如果数组长度为 0 怎么办？

A：题目约束1 <= nums.length，所以无需处理。但健壮代码可加 assert 或注释说明。

Q：你的标记法在全是负数的数组上表现如何？

A：非常好！

• 第一步将所有负数变为 n+1
• 第二步无任何标记操作（因 n+1 > n）
• 第三步发现 nums[0] > 0 → 返回 1，正确。

十一、这道算法题在实际开发中的应用

虽然“找缺失的第一个正数”看似抽象，但其思想在多个领域有实际价值：

1. 资源分配与ID生成

• 系统需为新用户分配最小可用ID（从1开始）
• 已分配的ID存储在数据库或缓存中
• 本题算法可用于快速定位下一个可用ID（尤其在内存中维护ID池时）

2. 游戏开发中的物品槽位管理

• 玩家背包有 N 个槽位，每个物品占一个槽
• 需要找到第一个空槽来放置新物品
• 若用数组表示槽位占用（1=占用，0=空），则本题等价于找第一个0的位置+1

3. 分布式系统中的节点编号

• 集群节点编号从1开始连续分配
• 当节点宕机后重启，需重新获取最小可用编号
• 本地缓存可用编号列表，用本题算法快速计算

4. 数据校验与完整性检测

• 日志文件按序号命名：log_1.txt, log_2.txt, …
• 检测是否有缺失的日志文件
• 将现有日志序号读入数组，用本题算法找第一个缺失序号

5. 内存池管理（简化模型）

• 内存块编号为 1,2,3,…,N
• 分配时找最小可用块号
• 释放时标记为可用
• 本题算法可作为快速分配策略的基础

📌 核心价值：在有限连续编号空间中，高效定位第一个空缺位置

十二、相关题目推荐

掌握本题后，可挑战以下变种或进阶题：

十三、总结与延伸

核心收获

1. 原地哈希是解决“有限解空间 + O(1) 空间”问题的利器
2. 利用数组下标与值的映射，可将数组变为哈希表
3. 符号位、置换、偏移是三种常见的原地标记技术
4. 边界条件（如重复、全负、全大数）必须充分测试

延伸思考

• 能否扩展到找前 K 个缺失正数？
  → 可以，但需 O(k) 空间存储结果，或多次调用本算法

• 如果数组是只读的，但允许 O(√n) 空间？
  → 可用分块思想：将 [1,n] 分成 √n 块，统计每块出现次数，再细查

• 流式数据场景：数字逐个到来，如何实时维护“当前缺失的最小正数”？
  → 需要更复杂的数据结构（如并查集维护连续区间），超出本题范围

最后建议

• 面试时：先分析解空间 [1, n+1]，再提出原地哈希思路
• 刷题时：手动模拟两种方法的执行过程，加深理解
• 工程中：若允许修改数组，优先用标记法；否则用哈希表

结语：“缺失的第一个正数”是 LeetCode 中一道极具代表性的难题，它完美展示了如何在严苛的时空限制下，通过巧妙利用输入结构本身来突破常规。掌握它，你不仅学会了一道题，更掌握了一种在资源受限环境下进行高效计算的思维方式。

愿你在算法征途中，永不缺失灵感与勇气！🚀

字数统计：约 9300 字（含代码与表格）
适用读者：LeetCode 刷题者、Java 开发者、算法面试准备者
版权声明：本文为原创技术博客，转载请注明出处。