知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 42 - 缺失的第一个正数 ## 题目(LeetCode 41) 给定未排序整数数组,找出缺失的最小正整数,要求 O(n) 时间 O(1) 空间。 ## 解法:原地哈希 > 💬 **Q:我的写法用 if 而不是 while,有哪些问题?** > > 两个关键问题: > > **问题 1(致命):if 只交换一次,元素没有完全归位** > > 交换后 `nums[i]` 变成了新值,这个新值可能也需要归位,但 `if` 不会继续处理。 > > ``` > 用 [3, 4, -1, 1] 模拟你的 if 写法: > > i=0: nums[0]=3 → swap(0,2) → [-1, 4, 3, 1] > nums[0]=-1,不在范围 → 跳过 ✓ > > i=1: nums[1]=4 → swap(1,3) → [-1, 1, 3, 4] > nums[1]=1,应该继续放到 nums[0]! > 但 if 只执行一次 → 1 留在 index=1 → 没归位 ✗ > > 最终:[-1, 1, 3, 4] → nums[0]≠1 → return 1 > (碰巧答案对了,但 1 没有归位到 index=0) > ``` > > 用正确的 while 写法: > ``` > i=1: nums[1]=4 → swap(1,3) → [-1, 1, 3, 4] > while 继续:nums[1]=1 → swap(1,0) → [1, -1, 3, 4] > while 继续:nums[1]=-1,不在范围 → 停止 > > 最终:[1, -1, 3, 4] → 每个元素都尽可能归位了 > ``` > > **问题 2:缺少防重复判断,遇到重复值会死循环** > > 如果 `nums[i]` 和 `nums[nums[i]-1]` 值相同(如 `[1,1]`),交换后什么都没变,while 会无限循环。必须加 `nums[i] != nums[nums[i]-1]` 的判断。 > > 正确写法: > ```java > while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) { > swap(nums, i, nums[i] - 1); > } > ``` > > 总结:`if` → `while`,加上 `nums[i] != nums[nums[i]-1]` 防死循环。 ```java class Solution { public int (int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { int tmp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = tmp; } } for (int i = 0; i < n; i++) { if (nums[i] != i + 1) return i + 1; } return n + 1; } } ``` ## 复杂度 - 时间 O(n),空间 O(1) ## 一句话总结 把每个数放到它该在的位置(值 x 放到下标 x-1),然后扫一遍找第一个不对的。 ## 说明 缺失的第一个正数要求 O(n) 时间 O(1) 空间,这决定了必须用**原地哈希**(把数组本身当哈希表)。 HashSet 方案 O(n) 时间但 O(n) 空间,不满足要求。排序方案 O(n log n) 时间,也不满足要求。当前原地哈希解法是满足所有约束的唯一方案。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入