企业官网建设流程全解析

大型网站开发报价方案,影视制作公司简介,wordpress 评论 顶踩 心 插件,wordpress 阿里云景象「缺失的第一个正数」核心考察原地哈希的创新应用与空间复杂度优化思路。这道题的巧妙之处在于#xff0c;在严格的时间#xff08;O (n)#xff09;和空间#xff08;O (1) 额外空间#xff09;限制下#xff0c;需要跳出常规哈希表的思维定式#xff0c;利用数组本身作…「缺失的第一个正数」核心考察原地哈希的创新应用与空间复杂度优化思路。这道题的巧妙之处在于在严格的时间O (n)和空间O (1) 额外空间限制下需要跳出常规哈希表的思维定式利用数组本身作为哈希容器。实际开发中类似 数据完整性校验、缺失数据快速定位 等场景都能用到它的核心逻辑。今天我们从最直观的暴力解法出发一步步优化到符合所有限制的最优解带你吃透这道题的设计精髓 题目重述给你一个未排序的整数数组nums请你找出其中没有出现的最小正整数。这里有两个严格限制时间复杂度必须为 O (n)不能用排序等 O (n log n) 的方法只使用常数级别O (1)的额外空间不能用常规哈希表存储所有元素。举个例子输入nums [1,2,0]输出31 和 2 都存在最小缺失的正整数是 3输入nums [3,4,-1,1]输出21 存在2 缺失输入nums [7,8,9,11,12]输出1最小的正整数 1 都不存在。 阶梯思路拆解第一步暴力思路枚举 线性查找最直观的想法是从最小的正整数 1 开始依次判断每个正整数是否在数组中存在第一个不存在的就是答案。这种方法完全贴合题目描述但效率极低仅适合理解题目本质。 核心逻辑从target1开始依次递增对每个target遍历数组判断是否存在该元素若不存在直接返回target若存在target继续判断循环往复直到找到答案。 图文演示以 nums [3,4,-1,1] 为例如图所示暴力查找过程target1遍历数组找到 1存在→ target2target2遍历数组未找到 2不存在→ 返回 2最终结果2。✅ 代码实现JavapublicclassSolution{publicintfirstMissingPositive(int[]nums){inttarget1;while(true){// 遍历数组判断target是否存在booleanexistsfalse;for(intnum:nums){if(numtarget){existstrue;break;}}if(!exists){returntarget;}target;}}}⚙️ 复杂度分析复杂度类型计算结果说明时间复杂度O(n×k)k 是缺失的第一个正整数最坏情况下 kn1如数组是 [1,2,3]此时时间复杂度为 O (n²)空间复杂度O(1)仅使用常数个临时变量target、exists符合空间限制 遇到的问题时间效率过低当数组长度n10⁵且数组是[1,2,...,10⁵]时需要遍历 10⁵1 次每次遍历数组 10⁵个元素总运算量达到 10¹⁰ 次完全超出时间限制。核心问题是重复遍历数组—— 每次判断 target 都要重新扫描整个数组做了大量无用功。我们需要一种方式能在 O (1) 时间内判断元素是否存在这就是哈希表的核心价值但常规哈希表会占用 O (n) 空间不符合要求。因此我们需要原地哈希 —— 利用数组本身存储存在的正整数。第二步优化思路哈希表存储 空间换时间️核心想法是用一个哈希表存储数组中所有的正整数然后从 1 开始依次判断每个正整数是否在哈希表中第一个不存在的就是答案。这种方法能将时间复杂度降到 O (n)但需要额外的 O (n) 空间不符合 常数级额外空间 的要求仅作为过渡思路。 核心逻辑遍历数组将所有正整数存入哈希表过滤负数和 0因为它们不影响最小正整数的判断从target1开始依次判断target是否在哈希表中若不存在返回target若存在target继续判断若所有 1~n 的正整数都存在返回 n1。 图文演示以 nums [3,4,-1,1] 为例如图所示哈希表查找过程遍历数组存入哈希表的正整数{3,4,1}target1在哈希表中存在→ target2target2不在哈希表中不存在→ 返回 2最终结果2。✅ 代码实现Javaimportjava.util.HashSet;importjava.util.Set;publicclassSolution{publicintfirstMissingPositive(int[]nums){SetIntegerpositiveSetnewHashSet();// 存入所有正整数for(intnum:nums){if(num0){positiveSet.add(num);}}// 从1开始查找inttarget1;while(true){if(!positiveSet.contains(target)){returntarget;}target;}}}⚙️ 复杂度分析复杂度类型计算结果说明时间复杂度O(n)遍历数组存入哈希表 O (n)查找 target 最坏 O (n)如数组是 [1,2,…,n]整体 O (n)空间复杂度O(n)哈希表最多存储 n 个正整数不符合 “常数级额外空间” 的要求 优化亮点与待改进点亮点时间复杂度从 O (n²) 降到 O (n)彻底解决了重复遍历数组的问题待改进需要额外的 O (n) 空间存储哈希表不符合题目 常数级额外空间 的严格要求。我们需要将哈希表搬到原数组中实现原地存储。第三步最优解法原地哈希 索引映射这是本题的最优解核心思路是将数组本身作为哈希表利用正整数 x 应该放在索引 x-1 的位置的映射关系通过交换元素让数组满足nums[i] i1对于存在的正整数 x最后遍历数组找到第一个不满足该关系的索引 ii1 就是缺失的最小正整数。先理解核心映射关系对于数组中的正整数 x如果 x 在 [1, n] 范围内n 是数组长度那么它应该放在索引 x-1 的位置比如 x1→索引 0x2→索引 1x3→索引 2负数、0、大于 n 的数这些数不影响最小正整数的判断最小正整数一定在 [1, n1] 范围内因为如果 1~n 都存在答案就是 n1可以暂时留在原地。 核心逻辑遍历数组对每个元素nums[i]若nums[i]是正整数且在 [1, n] 范围内且nums[nums[i]-1] ! nums[i]目标位置的元素不是当前元素需要交换交换nums[i]和nums[nums[i]-1]将当前元素放到它应该在的位置注意交换后需要重新检查当前位置 i 的新元素因此用 while 循环遍历交换后的数组找到第一个满足nums[i] ! i1的索引 i返回 i1若所有元素都满足nums[i] i1返回 n1。 图文演示以 nums [3,4,-1,1] 为例n4如图所示原地哈希交换过程初始数组[3,4,-1,1]遍历 i0nums [i]33 是正整数且在 [1,4] 范围内目标位置是 3-12目标位置 nums [2] -1 ! 3交换 nums [0] 和 nums [2]交换后数组[-1,4,3,1]交换后的 nums [i]-1不满足交换条件继续遍历 i1遍历 i1nums [i]44 是正整数且在 [1,4] 范围内目标位置是 4-13目标位置 nums [3] 1 ! 4交换 nums [1] 和 nums [3]交换后数组[-1,1,3,4]交换后的 nums [i]1满足交换条件继续处理 i1处理 i1nums [i]11 是正整数且在 [1,4] 范围内目标位置是 1-10目标位置 nums [0] -1 ! 1交换 nums [1] 和 nums [0]交换后数组[1,-1,3,4]交换后的 nums [i]-1不满足交换条件继续遍历 i2遍历 i2nums [i]33 是正整数目标位置是 2nums [2]3无需交换遍历 i3nums [i]44 是正整数目标位置是 3nums [3]4无需交换交换后最终数组[1,-1,3,4]遍历数组查找缺失值i0nums [0]1 01 → 满足i1nums [1]-1 ! 11 → 不满足返回 112最终结果2。✅ 代码实现Java最优解publicclassSolution{publicintfirstMissingPositive(int[]nums){intnnums.length;// 第一步原地哈希交换让正整数归位for(inti0;in;i){// 循环交换当前元素是正整数、在[1,n]范围内、目标位置元素不相等while(nums[i]0nums[i]nnums[nums[i]-1]!nums[i]){// 交换nums[i]和nums[nums[i]-1]inttargetIndexnums[i]-1;inttempnums[i];nums[i]nums[targetIndex];nums[targetIndex]temp;}}// 第二步遍历数组找到第一个缺失的正整数for(inti0;in;i){if(nums[i]!i1){returni1;}}// 第三步所有1~n都存在返回n1returnn1;}}⚙️ 复杂度分析复杂度类型计算结果说明时间复杂度O(n)每个元素最多被交换一次归位后不会再被移动遍历数组两次整体线性时间空间复杂度O(1)仅使用常数个临时变量targetIndex、temp完全满足常数级额外空间要求✨ 核心优势时间最优O (n) 时间复杂度严格满足题目要求空间最优O (1) 额外空间复杂度完美解决空间限制逻辑巧妙利用索引映射实现原地哈希无需额外数据结构思路极具创新性。第四步边界情况与易错点常见边界场景数组全为负数如nums [-1,-2,-3]返回 1最小正整数 1 缺失数组包含 1~n 所有正整数如nums [1,2,3,4]返回 5n1数组有重复元素如nums [2,2,3]交换后数组为[2,2,3]i0 时 nums [0]2 ! 1返回 1数组长度为 1如nums [1]返回 2nums [0]返回 1nums [-5]返回 1。易错点提醒交换条件遗漏忘记判断nums[nums[i]-1] ! nums[i]导致重复交换陷入死循环忽略重复元素重复元素会导致交换后仍不满足nums[i] i1但不影响最终结果遍历时分能正确识别映射关系错误将 x 放在索引 x 的位置而非 x-1导致逻辑混乱未处理大于 n 的正整数这类数无需交换因为最小正整数一定在 [1,n1] 范围内留在原地即可。 总结「缺失的第一个正数」的解题核心是原地哈希的创新应用从暴力到最优的递进思路清晰暴力解法枚举 线性查找直观但效率低O (n²) 时间哈希表解法空间换时间效率提升但需 O (n) 空间原地哈希解法利用索引映射实现原地存储满足 O (n) 时间 O (1) 额外空间的严格要求。关键技巧核心映射正整数 x1≤x≤n应放在索引 x-1 的位置让数组成为 “天然哈希表”交换逻辑用 while 循环确保当前元素归位避免遗漏重复交换范围收缩最小正整数一定在 [1,n1] 范围内无需考虑大于 n 的正整数和非正整数。同类题扩展建议掌握了这道题的思路后可以尝试这些进阶题目都是同一类原地操作思维的应用LeetCode 287. 寻找重复数原地置换思路利用每个数应该在对应索引位置的映射关系LeetCode 448. 找到所有数组中消失的数字与本题思路几乎一致找出所有缺失的正整数LeetCode 765. 情侣牵手贪心 原地交换利用索引映射实现最优匹配LeetCode 136. 只出现一次的数字异或运算的原地操作虽思路不同但同样追求空间优化。这类空间受限的题目核心是复用现有空间通过创新的映射关系或运算避免额外数据结构的使用。吃透本题的逻辑能极大提升你的算法创新思维 关注不迷路算法学习更高效如果这篇拆解对你有帮助别忘了关注我的微信公众号【小镇冥想人】 后续会持续更新 LeetCode 高频题的阶梯式解题思路从暴力到最优解层层递进每道题都搭配详细图文和代码注释帮你轻松攻克算法难关。