企业官网建设流程全解析

网站的建设模式,建设网站模板,企业网站开发时间,yahoo网站提交Java版LeetCode热题100之“缺失的第一个正数”#xff1a;O(n)时间与O(1)空间的极致挑战 摘要#xff1a;本文深入剖析 LeetCode 第 41 题 “缺失的第一个正数”#xff0c;全面覆盖原题回顾、算法构思、两种主流解法#xff08;标记法与置换法#xff09;、代码实现、复杂…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, N1] 范围内为什么最理想情况数组恰好包含[1, 2, 3, ..., N]→ 缺失的是N1其他情况至少有一个数在[1, N]中缺失 → 答案 ∈[1, N]因此我们只需关注 [1, N] 范围内的数其他数≤0 或 N可忽略或处理。常见解法及其缺陷方法思路时间空间是否满足要求哈希表存所有数从1开始查O(n)O(n)❌空间超限排序 遍历排序后找缺口O(n log n)O(1)❌时间超限暴力枚举对每个 i∈[1,N1]遍历数组查是否存在O(n²)O(1)❌时间超限题目要求O(n) 时间 O(1) 空间意味着我们必须利用原数组本身作为辅助存储这引出了本题的核心思想原地哈希In-place Hashing三、答案构思核心思想原地哈希既然不能用额外空间建哈希表那就把原数组当作哈希表用如何做哈希表的作用快速判断“某个数是否存在”我们希望若数字x ∈ [1, N]存在则在数组的某个位置打上“存在标记”有两种主流实现方式方法一标记法利用符号位将数组中所有 ≤0 的数替换为N1使其无效化遍历数组对每个x ∈ [1, N]将nums[x-1]变为负数打标记最后找第一个正数的位置 → 即为缺失的最小正整数方法二置换法将数字放到正确位置遍历数组若nums[i] ∈ [1, N]且不在正确位置即nums[i] ! i1则将其交换到nums[nums[i]-1]重复此过程直到无法交换最终若nums[i] ! i1则i1缺失两种方法均满足 O(n) 时间、O(1) 空间但实现细节和鲁棒性略有不同。四、完整答案Java 实现方法一标记法推荐简洁稳定classSolution{publicintfirstMissingPositive(int[]nums){intnnums.length;// 第一步将所有非正数0替换为 n1使其无效for(inti0;in;i){if(nums[i]0){nums[i]n1;}}// 第二步遍历数组对每个在 [1, n] 范围内的数 x// 将 nums[x-1] 变为负数打标记for(inti0;in;i){intnumMath.abs(nums[i]);// 取绝对值防止已被标记为负if(numn){// 将对应位置的数变为负注意避免重复取负nums[num-1]-Math.abs(nums[num-1]);}}// 第三步找到第一个正数的位置返回 index 1for(inti0;in;i){if(nums[i]0){returni1;}}// 若全部为负说明 [1, n] 都存在返回 n1returnn1;}}方法二置换法巧妙但需防死循环classSolution{publicintfirstMissingPositive(int[]nums){intnnums.length;// 将每个在 [1, n] 范围内的数放到其“正确位置”for(inti0;in;i){// 循环交换直到 nums[i] 不在 [1, n] 或已在正确位置while(nums[i]0nums[i]nnums[nums[i]-1]!nums[i]){// 交换 nums[i] 和 nums[nums[i] - 1]inttempnums[nums[i]-1];nums[nums[i]-1]nums[i];nums[i]temp;}}// 遍历检查若 nums[i] ! i1则 i1 缺失for(inti0;in;i){if(nums[i]!i1){returni1;}}returnn1;}}✅建议面试时优先写方法一逻辑清晰、不易出错再提方法二作为优化或变体。五、代码分析方法一标记法详解步骤1无效化非目标数if(nums[i]0)nums[i]n1;目的确保后续只处理[1, n]的数为何用n1因为n1 n不会干扰[1, n]的标记步骤2打标记关键intnumMath.abs(nums[i]);if(numn){nums[num-1]-Math.abs(nums[num-1]);}取绝对值因为nums[i]可能已被前面的操作标记为负再次取绝对值再取负防止nums[num-1]已为负重复取负变正错误例如若nums[0] -3直接nums[0] -nums[0]会变成3丢失标记 这是最容易出错的地方必须用-Math.abs(...)确保结果为负。步骤3找第一个未标记位置正数表示该位置对应的数index1未出现全负 →[1, n]全出现 → 返回n1示例演示nums [3,4,-1,1]无效化[-1 → 5]→[3,4,5,1]打标记i0: num3 → nums[2] -5 →[3,4,-5,1]i1: num4 → nums[3] -1 →[3,4,-5,-1]i2: num54→ 跳过i3: num1 → nums[0] -3 →[-3,4,-5,-1]找正数nums[1] 4 0→ 返回11 2✅方法二置换法详解核心循环while(nums[i]0nums[i]nnums[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]i0: nums[0]3 → 应放位置2 → 交换 nums[0] 和 nums[2] →[-1,4,3,1]现在 nums[0]-1无效ii1: 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无效ii2: nums[2]3 → 已在位置23-12→ 跳过i3: nums[3]4 → 已在位置3 → 跳过最终[1,-1,3,4]→ 检查i0: 11 ✅i1: -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✅ 两种方法均严格满足题目要求。七、常见问题解答FAQQ1为什么答案一定在 [1, n1]A反证法。假设答案 n1即 [1, n1] 都在数组中但数组只有 n 个位置不可能容纳 n1 个不同的正整数矛盾故答案 ≤ n1又因正整数从 1 开始故答案 ∈ [1, n1]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]i0: 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) 空间解法依赖于修改原数组八、优化思路总结方案核心技巧优点缺点哈希表外部存储简单直观空间 O(n)排序有序查找易理解时间 O(n log n)标记法符号位作标记代码简洁、稳定、易调试需处理负号细节置换法数字归位思想巧妙、无需符号操作需防死循环、逻辑稍复杂工程建议优先选择标记法逻辑线性边界清晰适合生产环境置换法可作为面试中的“炫技”方案展示对数组操作的熟练度九、数据结构与算法基础知识点回顾1. 原地哈希In-place Hashing定义利用输入数组本身的下标作为哈希地址值作为存储内容前提问题的解空间有限如本题 [1, n1]实现方式利用符号位正/负利用偏移量加 n利用置换将值放到对应下标2. 数组索引与值的映射本题建立映射值 x ↔ 下标 x-1这是处理“1-based 正整数”与“0-based 数组”的标准技巧3. 边界条件处理空数组题目保证 n≥1无需考虑全负数如[-1,-2]→ 答案1全大于n如[5,6,7]n3→ 答案1包含1~n如[1,2,3]→ 答案44. 时间复杂度的“摊还分析”置换法的内层 while 看似嵌套但每个元素最多被移动一次总操作次数为 O(n)属于摊还 O(1)每次操作十、面试官提问环节模拟对话Q你的解法修改了原数组如果面试官要求不能修改呢A若不能修改原数组则无法同时满足 O(n) 时间和 O(1) 空间。我会说明这一点并给出两种妥协方案允许 O(n) 空间用 HashSetO(n) 时间允许 O(n log n) 时间先复制数组再排序O(1) 额外空间若不算复制Q方法一中如果数组里有 Integer.MAX_VALUE替换为 n1 会溢出吗A不会。因为n 10^5所以n1 100001远小于Integer.MAX_VALUE (≈2e9)。即使n10^5n1也安全。Q能否用位运算优化空间A理论上可以用位图Bitmap用一个 int 表示 32 个数的存在性。但需要(n31)/32个 int空间仍是 O(n)且题目要求 O(1) 空间位图不符合本题的 O(1) 解法必须依赖原数组Q如果数组长度为 0 怎么办A题目约束1 nums.length所以无需处理。但健壮代码可加 assert 或注释说明。Q你的标记法在全是负数的数组上表现如何A非常好第一步将所有负数变为 n1第二步无任何标记操作因 n1 n第三步发现 nums[0] 0 → 返回 1正确。十一、这道算法题在实际开发中的应用虽然“找缺失的第一个正数”看似抽象但其思想在多个领域有实际价值1. 资源分配与ID生成系统需为新用户分配最小可用ID从1开始已分配的ID存储在数据库或缓存中本题算法可用于快速定位下一个可用ID尤其在内存中维护ID池时2. 游戏开发中的物品槽位管理玩家背包有 N 个槽位每个物品占一个槽需要找到第一个空槽来放置新物品若用数组表示槽位占用1占用0空则本题等价于找第一个0的位置13. 分布式系统中的节点编号集群节点编号从1开始连续分配当节点宕机后重启需重新获取最小可用编号本地缓存可用编号列表用本题算法快速计算4. 数据校验与完整性检测日志文件按序号命名log_1.txt, log_2.txt, …检测是否有缺失的日志文件将现有日志序号读入数组用本题算法找第一个缺失序号5. 内存池管理简化模型内存块编号为 1,2,3,…,N分配时找最小可用块号释放时标记为可用本题算法可作为快速分配策略的基础 核心价值在有限连续编号空间中高效定位第一个空缺位置十二、相关题目推荐掌握本题后可挑战以下变种或进阶题题目链接关联点41. 缺失的第一个正数LeetCode 41本题448. 找到所有数组中消失的数字LeetCode 448同样用原地哈希标记法442. 数组中重复的数据LeetCode 442原地哈希找重复268. 丢失的数字LeetCode 268异或或求和但空间更宽松287. 寻找重复数LeetCode 287快慢指针 or 原地哈希剑指 Offer 03. 数组中重复的数字牛客网类似思想十三、总结与延伸核心收获原地哈希是解决“有限解空间 O(1) 空间”问题的利器利用数组下标与值的映射可将数组变为哈希表符号位、置换、偏移是三种常见的原地标记技术边界条件如重复、全负、全大数必须充分测试延伸思考能否扩展到找前 K 个缺失正数→ 可以但需 O(k) 空间存储结果或多次调用本算法如果数组是只读的但允许 O(√n) 空间→ 可用分块思想将 [1,n] 分成 √n 块统计每块出现次数再细查流式数据场景数字逐个到来如何实时维护“当前缺失的最小正数”→ 需要更复杂的数据结构如并查集维护连续区间超出本题范围最后建议面试时先分析解空间 [1, n1]再提出原地哈希思路刷题时手动模拟两种方法的执行过程加深理解工程中若允许修改数组优先用标记法否则用哈希表结语“缺失的第一个正数”是 LeetCode 中一道极具代表性的难题它完美展示了如何在严苛的时空限制下通过巧妙利用输入结构本身来突破常规。掌握它你不仅学会了一道题更掌握了一种在资源受限环境下进行高效计算的思维方式。愿你在算法征途中永不缺失灵感与勇气字数统计约 9300 字含代码与表格适用读者LeetCode 刷题者、Java 开发者、算法面试准备者版权声明本文为原创技术博客转载请注明出处。