【力扣100题】60.缺失的第一个正数

题目描述给你一个未排序的整数数组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解题思路总览方法核心思想时间复杂度空间复杂度备注原地哈希将每个数放到它值对应的位置O(n)O(1)推荐解法哈希表用额外空间记录出现过的数O(n)O(n)简单但空间不优排序后遍历先排序再找缺失O(n log n)O(1)时间不优一、核心解法原地哈希桶排序思想核心思想将数组本身作为哈希表。对于每个位置 i我们希望nums[i] i 1。如果1 nums[i] n则它应该放在索引nums[i] - 1的位置通过原地交换将每个数放到它值对应的位置最后遍历数组第一个不满足nums[i] i 1的位置答案就是i 1关键洞察观察答案一定在 [1, n1] 范围内 原因 - 如果 [1, n] 都在数组中答案是 n1 - 否则缺失的最小正整数一定在 [1, n] 中 因此我们只需要关心 [1, n] 范围内的数其他数0 或 n可以直接忽略。图解输入: nums [3, 4, -1, 1] 初始状态: index: 0 1 2 3 nums: [3, 4, -1, 1] i0 处理 i0: nums[0] 3 3 0 3 4 nums[2] ! 3 (nums[2] -1) swap(nums[2], nums[0]) nums [-1, 4, 3, 1] 处理 i0: nums[0] -1 -1 不满足 0跳过 处理 i1: nums[1] 4 4 0 4 4 nums[3] ! 4 (nums[3] 1) swap(nums[3], nums[1]) nums [-1, 1, 3, 4] 处理 i1: nums[1] 1 1 0 1 4 nums[0] ! 1 (nums[0] -1) swap(nums[0], nums[1]) nums [1, -1, 3, 4] 处理 i1: nums[1] -1 -1 不满足 0跳过 处理 i2, 3: nums[2] 3, nums[2] 3, 跳过 nums[3] 4, nums[3] 4, 跳过 最终状态: index: 0 1 2 3 nums: [1, -1, 3, 4] i1 不满足 nums[i] i1 遍历结果: i0: nums[0]1, i11, 满足 i1: nums[1]-1, i12, 不满足返回 2二、算法流程图输入: nums [3, 4, -1, 1], n 4 第一步原地交换将每个数放到正确位置 初始化: nums [3, 4, -1, 1] i 0 i0: nums[0]3, 3在[1,4]内, nums[2]-1 ! 3 交换: [3,4,-1,1] - [-1,4,3,1] nums[0]-1, 不满足0, 跳过 i1: nums[1]4, 4在[1,4]内, nums[3]1 ! 4 交换: [-1,4,3,1] - [-1,1,3,4] nums[1]1, 1在[1,4]内, nums[0]-1 ! 1 交换: [-1,1,3,4] - [1,-1,3,4] i1: nums[1]-1, 不满足0, 跳过 i2: nums[2]3, 3在[1,4]内, nums[2]3 3, 不交换 i3: nums[3]4, 4在[1,4]内, nums[3]4 4, 不交换 第二步遍历找缺失 i0: nums[0]1, i11, 满足 i1: nums[1]-1, i12, 不满足 输出: 2三、完整代码实现classSolution{public:intfirstMissingPositive(vectorintnums){intnnums.size();// 第一步原地哈希// 将每个在 [1, n] 范围内的数放到它值对应的位置for(inti0;in;i){// 注意要用 while 而不是 if因为交换后可能还需要继续处理while(nums[i]0nums[i]nnums[nums[i]-1]!nums[i]){// 交换 nums[i] 和 nums[nums[i] - 1]// 把 nums[i] 放到索引为 nums[i] - 1 的位置swap(nums[nums[i]-1],nums[i]);}}// 第二步遍历找缺失for(inti0;in;i){if(nums[i]!i1){returni1;}}// 如果 [1, n] 都在返回 n1returnn1;}};四、逐行解析for(inti0;in;i){遍历数组的每个位置while(nums[i]0nums[i]nnums[nums[i]-1]!nums[i]){nums[i] 0只处理正数nums[i] n只处理在 [1, n] 范围内的数答案只可能在范围内nums[nums[i] - 1] ! nums[i]目标位置不是正确的值需要交换用 while 而不是 if因为交换后当前位置可能还是需要处理的数swap(nums[nums[i]-1],nums[i]);将nums[i]放到索引nums[i] - 1的位置例如nums[i] 3则放到索引 2 的位置for(inti0;in;i){if(nums[i]!i1){returni1;}}遍历数组第一个不满足nums[i] i 1的位置答案就是i 1returnn1;如果所有位置都满足返回 n 1例如 [1,2,3] 缺失的是 4五、为什么 while 而不是 if错误示例用 if: nums [4, 2, 1] i0: nums[0]4, 交换 - [1, 2, 4] 此时 nums[0]1已经在正确位置 但 nums[2]4应该检查但用 if 不会继续检查 正确示例用 while: nums [4, 2, 1] i0: nums[0]4, 交换 - [1, 2, 4] 此时 nums[0]1满足 nums[0]1跳出 while 用 while 可以继续检查交换后的 nums[i] 关键点 while 确保当前位置的数被处理到正确为止 if 可能会漏掉交换后的数六、原地哈希的原理原地哈希本质上是桶排序的思想 普通哈希表 值 v 存储在 hash[v] 的位置 需要额外的数组 原地哈希 值 v 存储在索引 v-1 的位置 直接利用原数组的空间 示例 如果数组中有数字 3就把它放到 nums[2]即 3-1的位置 检查 nums[i] 是否等于 i1 就能知道 i1 是否存在七、复杂度分析方法时间复杂度空间复杂度备注原地哈希O(n)O(1)推荐哈希表O(n)O(n)空间不优排序遍历O(n log n)O(1)时间不优详细分析时间复杂度 第一步每个元素最多被交换一次放到正确位置后就不会再处理 即使 while 循环总交换次数 n 第二步遍历 O(n) 总计O(n) 空间复杂度 只用了几个变量n, i 等 没有使用额外的数组 O(1)八、边界情况分析情况处理方式空数组return 1[1]第一步不做交换第二步 return 2[2]第一步不做交换2 n1第二步 return 1[-1, -2, -3]第一步不做交换无正数第二步 return 1[1, 2, 3]第一步排好序第二步 return 4示例分析示例1: nums [1,2,0] 原地哈希后: [1,2,0] 遍历: i2, nums[2]0 ! 3 返回: 3 示例2: nums [3,4,-1,1] 原地哈希后: [1,-1,3,4] 遍历: i1, nums[1]-1 ! 2 返回: 2 示例3: nums [7,8,9,11,12] 原地哈希后: [7,8,9,11,12] (无变化) 遍历: i0, nums[0]7 ! 1 返回: 1九、面试追问 FAQ问题回答要点Q: 为什么只关心 [1, n] 范围内的数答案只可能在 [1, n1] 范围内因为如果 [1,n] 都在答案是 n1Q: 为什么用 while 而不是 if因为交换后当前位置可能还是需要处理的数必须继续检查Q: nums[nums[i]-1] 会不会越界不会因为条件nums[i] n保证nums[i]-1 n-1且nums[i] 0保证nums[i]-1 0Q: 能否用 set 解决可以但空间复杂度 O(n)不满足要求Q: 时间复杂度为什么是 O(n)每个元素最多交换一次总交换次数 nQ: 如何证明空间是 O(1)只用了常数个变量没有使用与 n 相关的额外空间十、相关题目题目编号题目名称难度核心差异41缺失的第一个正数困难原地哈希442数组中重复的数据中等原地标记448找到所有失踪的数字简单原地标记268缺失数字简单异或或求和剑指 Offer 03数组中重复的数字简单原地哈希变形十一、总结要点内容核心思想原地哈希将数组当作哈希表使用关键洞察答案在 [1, n1] 范围内算法第一步将 [1,n] 范围内的数放到正确位置算法第二步遍历找第一个不满足 nums[i] i1 的位置时间复杂度O(n)每个元素最多交换一次空间复杂度O(1)原地操作关键点用 while 而非 if确保数被处理到正确位置易错点忽略 nums[nums[i]-1] 的边界检查缺失的第一个正数是经典的原地哈希问题核心思想是将数组本身作为哈希表利用索引来表示数是否出现过。难点在于理解原地交换的逻辑和为什么用 while 而不是 if。