题目描述
思路解析动画文字版
记住这句「slow 守保留区末尾、fast 找不等于 val 的值搬过来」,下面每一帧都在套它。
快指针 fast 走到下标 0,值 3 不等于 val(2)——这是要保留的值,准备搬到保留区位置 0。
把保留值 3 搬到 nums[0],慢指针 slow 前移到 1。保留区现在是 [3]。
快指针 fast 走到下标 1,值 2 正好等于 val(2)——要移除的值,slow 不动,直接跳过。
快指针 fast 走到下标 2,值 0 不等于 val(2)——这是要保留的值,准备搬到保留区位置 1。
把保留值 0 搬到 nums[1],慢指针 slow 前移到 2。保留区现在是 [3,0]。
快指针 fast 走到下标 3,值 2 正好等于 val(2)——要移除的值,slow 不动,直接跳过。
快指针 fast 走到下标 4,值 4 不等于 val(2)——这是要保留的值,准备搬到保留区位置 2。
把保留值 4 搬到 nums[2],慢指针 slow 前移到 3。保留区现在是 [3,0,4]。
快指针 fast 走到下标 5,值 2 正好等于 val(2)——要移除的值,slow 不动,直接跳过。
快指针 fast 走到下标 6,值 1 不等于 val(2)——这是要保留的值,准备搬到保留区位置 3。
把保留值 1 搬到 nums[3],慢指针 slow 前移到 4。保留区现在是 [3,0,4,1]。
快指针 fast 走到下标 7,值 5 不等于 val(2)——这是要保留的值,准备搬到保留区位置 4。
把保留值 5 搬到 nums[4],慢指针 slow 前移到 5。保留区现在是 [3,0,4,1,5]。
快指针 fast 走到下标 8,值 2 正好等于 val(2)——要移除的值,slow 不动,直接跳过。
快指针 fast 走到下标 9,值 6 不等于 val(2)——这是要保留的值,准备搬到保留区位置 5。
把保留值 6 搬到 nums[5],慢指针 slow 前移到 6。保留区现在是 [3,0,4,1,5,6]。
快指针 fast 走到下标 10,值 2 正好等于 val(2)——要移除的值,slow 不动,直接跳过。
快指针 fast 走到下标 11,值 7 不等于 val(2)——这是要保留的值,准备搬到保留区位置 6。
把保留值 7 搬到 nums[6],慢指针 slow 前移到 7。保留区现在是 [3,0,4,1,5,6,7]。
快指针扫完整个数组,慢指针停在 7。前 7 个 [3,0,4,1,5,6,7] 就是保留结果,返回长度 7(下标 7 之后的旧值不用管)。
边界先想清:空数组返回 0;全是 val 时保留区为空、返回 0。
两个高频追问:指针含义,以及保留元素的相对顺序保持不变。
参考代码
def removeElement(nums, val): slow = 0 # 保留区下一个写入位 for fast in range(len(nums)): if nums[fast] != val: # 不等于 val 才保留 nums[slow] = nums[fast] # 搬过来 slow += 1 return slow # 新长度复杂度
- 时间:O(n),fast 把数组扫一遍,每个元素只看一次
- 空间:O(1),原地在 nums 上覆盖保留值,不开新数组
易错点
面试追问把动画讲成自己的话
追问slow 和 fast 各代表什么?
追问保留下来的元素顺序会变吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
找出字符串中第一个匹配项的下标
LeetCode 28 · 中等 · 沿着 数组 & 哈希 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题