题目描述
思路解析动画文字版
因为相同数字都挨在一起,只要看结果数组里倒数第二个数,就能知道当前 x 是否会成为第三份重复。
如果 x == nums[slow-2],说明结果末尾已经有两个 x,再写就会变成第三个,必须跳过。
初始化:slow=0,准备扫描:slow 左边是已经整理好的结果区,slow 自己指向下一次写入位置。
读第一个 1:slow<2,保留:前两个元素不可能违反“最多两次”,第一个 1 直接保留。
读第二个 1:slow 仍小于 2,保留:第二个 1 也允许保留。现在结果区是 [1,1]。
读第三个 1:先比较 nums[slow-2]:slow=2 时,slow-2=0。结果区倒数第二个数已经是 1,如果再写当前 1,就会出现三个 1。
跳过第三个 1:slow 不动:跳过只是不写入当前 x,扫描继续往后走。结果区仍然是 [1,1]。
读第一个 2:和 nums[slow-2]=1 不同,保留:当前 x=2,结果区倒数第二个是 1,不会形成第三个 2,所以写到 nums[2]。
读第二个 2:仍然可以保留:写第二个 2 前,nums[slow-2]=nums[1]=1,不等于 2,所以第二个 2 合法。
读 3:和 nums[slow-2]=2 不同,保留:3 第一次出现,当然可以保留。结果区变成 [1,1,2,2,3]。
返回 slow=5:返回长度 5。下标 5 之后的内容不重要,LeetCode 只检查前 5 个位置。
本题 k=2,所以检查 nums[slow-2]。
参考代码
class Solution: def removeDuplicates(self, nums): slow = 0 for x in nums: if slow < 2 or x != nums[slow - 2]: nums[slow] = x slow += 1 return slow复杂度
- 时间复杂度:O(n),每个元素扫描一次。
- 空间复杂度:O(1),原地覆盖,只使用 slow 和当前 x。
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
轮转数组
LeetCode 189 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题