DAY10: LeetCode 26 + 80｜删除有序数组重复项：从 `i - 1` 一步推到 `i - k`

LeetCode 26 + 80｜删除有序数组重复项：从 i – 1 一步推到 i – k

这两道题放在一起看会比较有意思。

LeetCode 26 要求：每个数字最多保留 1 个 LeetCode 80 则变成：每个数字最多保留 2 个

一开始我以为只是把“去重”稍微改一下，但真正写到第二题时才发现：

如果还按照第一题的方式和前一个数字比较，第二个重复值也会被误删。

最后把两题放在一起，反而可以得到一个很统一的规律：

最多保留 1 个 → 看 i – 1
最多保留 2 个 → 看 i – 2
最多保留 k 个 → 看 i – k

这篇主要记录这个思路是怎么一步一步推出来的。

LeetCode 26：LeetCode 26

LeetCode 80：LeetCode 80

文章目录

• LeetCode 26 + 80｜删除有序数组重复项：从 `i – 1` 一步推到 `i – k`
• 一、这两道题为什么可以用双指针？
• 二、先统一两个指针的含义
• 三、LeetCode 26：每个数字最多保留 1 个
• • 第一步：第一个数字一定可以保留
  • 怎么判断 nums[j] 要不要保留？
  • 用一个例子走一遍
  • LeetCode 26 完整代码
• 四、来到 LeetCode 80：现在允许出现两次
• • 那怎么判断它会不会成为第 3 个？
  • 如果真的已经有两个相同数字呢？
  • 用完整例子走一遍
  • LeetCode 80 完整代码
• 五、把 26 和 80 放在一起看
• • LeetCode 26
  • LeetCode 80
  • 通用的 `i – k` 模板
  • 这个方法成立 -> 有序是关键
• 六、时间复杂度和空间复杂度

一、这两道题为什么可以用双指针？

两道题都有两个很重要的条件：

1. 数组已经按照递增顺序排列
26：非严格递增
80：有序数组
2. 要求原地修改数组

先看：递增

意思就是：

从小到大排列

但允许相等 –> 非严格

例如：

[0, 0, 0, 1, 1, 2, 3, 3]

因为数组已经有序，所以相同数字一定会挨在一起。

这就给了我们一个很重要的条件：

只需要一路向后扫描，就可以判断当前数字是不是应该保留。

另外题目要求：

原地修改

也就是说不能简单地重新创建一个结果数组，再把答案放进去。

所以可以考虑：

一个指针负责向后寻找
另一个指针负责往前写入

这就是这两道题的快慢双指针。

二、先统一两个指针的含义

为了方便后面从 26 推到 80，我把两道题里的 i 和 j 都统一成同一个含义。

j → 负责向后扫描原数组

i → 下一个可以写入的位置

也就是说：

nums[0:i]

始终表示：

已经整理好的有效区域。

注意这里 Python 切片：

nums[0:i]

是不包含 i 的。

所以如果：

i = 3

说明：

nums[0]
nums[1]
nums[2]

已经是整理好的部分。

一共有：

3 个有效元素

而：

nums[3]

正好就是下一个准备写入的位置。

因此：

当 i 被定义为“下一个写入位置”时，最后的 i 本身也正好等于有效元素数量。 因为数组下标从 0 开始。

所以最终可以直接：

return i

三、LeetCode 26：每个数字最多保留 1 个

先看第一道题。

例如：

nums = [0,0,1,1,1,2,2,3,3,4]

题目希望数组前面最终变成：

[0,1,2,3,4,…]

也就是说：

每个数字只保留 1 个

第一步：第一个数字一定可以保留

因为数组至少有一个元素，所以：

nums[0]

一定可以留下。

因此可以直接认为：

nums[0:1]

已经是整理好的区域。

也就是：

i = 1

此时：

i

指向：

下一个可以写入的位置

然后让：

j

从第二个数字开始寻找：

for j in range(1, len(nums)):

怎么判断 nums[j] 要不要保留？

因为这道题：

每个数字只能出现 1 次

所以当前的：

nums[j]

只需要和：

最后一个已经保留下来的数字

比较。

而已经整理好的区域是：

nums[0:i]

最后一个有效元素下标就是：

i – 1

所以判断：

nums[j] != nums[i – 1]

如果不同：

说明出现了一个新的数字

那就应该把它写到：

下一个可以写入的位置 i

也就是：

nums[i] = nums[j]

然后：

i += 1

把写入位置继续向后移动。

用一个例子走一遍

例如：

nums = [0,0,0,1,1,2]

开始：

i = 1

可以理解成：

[0 | 0,0,1,1,2]
↑
i

前面的：

0

已经保留。

j = 1

当前：

nums[j] = 0

最后一个保留值：

nums[i – 1] = nums[0] = 0

相同：

0 == 0

说明是重复值。

跳过。

j = 2

还是：

0

和最后一个保留值：

0

一样。

继续跳过。

j = 3

现在：

nums[j] = 1

而：

nums[i – 1] = 0

不同。

说明：

1

是一个新的数字。

所以：

nums[i] = nums[j]

也就是：

nums[1] = 1

数组前面变成：

[0,1,…]

然后：

i += 1

变成：

i = 2

后面继续

再次遇到：

1

因为：

1 == nums[i – 1]

跳过。

遇到：

2

因为：

2 != nums[i – 1]

写进去。

最后前面变成：

[0,1,2,…]

而：

i = 3

说明一共有：

3 个有效元素

所以直接：

return i

LeetCode 26 完整代码

class Solution:
def removeDuplicates(self, nums: List[int]) –> int:
i = 1

for j in range(1, len(nums)):
if nums[j] != nums[i – 1]:
nums[i] = nums[j]
i += 1

return i

整个过程可以简单记成：

j → 往后寻找新的数字

i → 指向下一个写入位置

而判断条件：

nums[j] != nums[i – 1]

实际上是在问：

当前数字和最后一个已经保留的数字不同吗？

如果不同：

就是新数字 → 保留

四、来到 LeetCode 80：现在允许出现两次

第二题和第一题很像。

但规则变成：

每个数字最多保留 2 个

例如：

[1,1,1,1,2,3,3]

最终应该变成：

[1,1,2,3,3,…]

这里真正麻烦的地方也出现了。

如果继续沿用 26 的判断：

nums[j] != nums[i – 1]

就会出问题:

假设现在已经整理成：

[1,1,2,3,…]

现在又遇到一个：

3

如果按照第一题的判断：

当前 3
和
前一个 3

相同。

那么就会认为：

重复了 → 跳过

但这是错的。

因为这道题允许：

3 出现两次

所以：

3,3

完全合法。

这说明：

LeetCode 80 不能再通过 “是否和前一个一样” 判断要不要保留。

真正应该问的是：

如果我把当前数字放进去，它会不会成为第 3 个相同数字？

那怎么判断它会不会成为第 3 个？

例如已经整理好的部分是：

[1,1,2,3]

现在又来了：

3

当前下一个写入位置：

i = 4

如果我们只看：

i – 1

得到的是：

nums[3] = 3

当然相同。

但这只能证明：

前面已经有 1 个 3

这并不违规。

我们真正关心的是：

前面是不是已经有两个 3？

所以应该再往前看一位：

i – 2

现在：

i = 4

所以：

i – 2 = 2

而：

nums[2] = 2

当前：

nums[j] = 3

于是：

3 != 2

说明：

当前这个 3 放进去以后，
最多只是第二个 3

所以可以保留。

最终：

[1,1,2,3,3]

正好合法。

如果真的已经有两个相同数字呢？

例如：

[1,1,…]

此时：

i = 2

又来了一个：

1

比较：

nums[j]
和
nums[i – 2]

也就是：

1
和
nums[0]

结果：

1 == 1

这说明：

在当前写入位置之前，
已经有两个 1 被保留下来了

如果再写当前这个：

1

就会变成：

1,1,1

也就是第 3 个。

所以不能保留。

用完整例子走一遍

例如：

nums = [1,1,1,1,2,3,3]

因为最多允许两个，所以前两个元素无论如何都可以保留。

因此：

i = 2

前面：

[1,1]

已经是有效区域。

让 j 从 2 开始。

j = 2

当前：

nums[j] = 1

比较：

nums[i – 2] = nums[2-2] = nums[0] = 1

于是：

1 == 1

说明如果再放进去，就会成为第 3 个 1。

跳过。

j = 3

还是：

1

因为前面没有写入新元素，所以：i 仍然是 2

继续比较：

nums[i – 2] = nums[0] = 1

还是相同。

继续跳过。

j = 4

当前：

nums[j] = 2

比较：

nums[i – 2] = nums[0] = 1

不同：

2 != 1

说明 2 可以保留。

所以：

nums[i] = nums[j]

变成：

[1,1,2,…]

然后：

i = i + 1 = 3

j = 5

当前值为：

nums[j] = 3

比较：

nums[i – 2] = numms[3-2] = nums[1] = 1

于是：

3 != 1

可以保留。

变成：

[1,1,2,3,…]

然后：

i = i + 1 = 4

j = 6

又来了一个：

3

看：

nums[i – 2] = nums[4-2] = 2

于是：

3 != 2

说明当前这个 3 只是第二个 3。

可以保留。

最终：

[1,1,2,3,3,…]

正好符合题目要求。

LeetCode 80 完整代码

class Solution:
def removeDuplicates(self, nums: List[int]) –> int:
n = len(nums)

if n <= 2:
return n

i = 2

for j in range(2, n):
if nums[j] != nums[i – 2]:
nums[i] = nums[j]
i += 1

return i

这里：

i → 下一个可以写入的位置

j → 负责扫描原数组

而：

nums[j] != nums[i – 2]

其实是在判断：

当前数字如果写进去，会不会成为第 3 个？

如果：

不等于 i – 2 位置的数字

说明还没有超过允许的两个。

所以可以写入。

五、把 26 和 80 放在一起看

现在再回头看两道题。

LeetCode 26

要求：

最多保留 1 个

所以：

i = 1

当前数字要不要保留，看：

nums[i – 1]

也就是：

已经保留区域中往前第 1 个数字。

代码：

if nums[j] != nums[i – 1]:

LeetCode 80

要求：

最多保留 2 个

所以：

i = 2

当前数字要不要保留，看：

nums[i – 2]

也就是：

已经保留区域中往前第 2 个数字。

代码：

if nums[j] != nums[i – 2]:

放在一起：

最多保留 1 个
↓
看 i – 1

最多保留 2 个
↓
看 i – 2

到这里其实已经很容易发现规律了。

如果题目变成“最多保留 k 个”呢？

假设题目规定：

每个数字最多可以出现 k 次

那么前：

k 个元素

一定可以直接保留。

所以：

i = k

然后对于后面的：

nums[j]

真正需要判断的是：

当前数字如果再写进去，会不会成为第 k + 1 个？

因此只需要看：

nums[i – k]

如果：

nums[j] == nums[i – k]

说明：

前面已经保留了 k 个相同数字

再写进去就超出限制。

所以跳过。

反过来：

nums[j] != nums[i – k]

说明当前数字还没有达到 k 个。

可以写入。

通用的 i – k 模板

于是可以抽象成：

def removeDuplicates(nums, k):
n = len(nums)

if n <= k:
return n

i = k

for j in range(k, n):
if nums[j] != nums[i – k]:
nums[i] = nums[j]
i += 1

return i

整个逻辑就是：

前 k 个元素 → 直接保留

后面的每个 nums[j]
↓
和 nums[i – k] 比较

相同
→ 如果放进去就会超过 k 个
→ 跳过

不同
→ 还没有超过 k 个
→ 写到 nums[i]
→ i += 1

这个方法成立 -> 有序是关键

这里还有一个不能忽略的前提：

数组是有序的

例如：

[1,1,1,2,2,3]

相同数字都会聚在一起。

因此，如果：

nums[j] == nums[i – k]

我们就可以确定：

在已经保留的区域里，当前数字已经至少出现了 k 次。

但如果数组是乱序的，例如：

[1,2,1,3,1]

相同数字没有连在一起，

那只通过：

nums[i – k]

就无法判断当前数字到底已经出现了多少次。

所以：

i – k 这种写法能够成立，一个非常重要的基础就是数组已经有序。

六、时间复杂度和空间复杂度

无论是 LeetCode 26 还是 LeetCode 80：j 都只会从左到右扫描一次数组。

所以：

时间复杂度：O(n)

整个过程只使用了：

i
j
n

这些额外变量。

没有创建与输入规模相关的新数组。

所以：

额外空间复杂度：O(1)

并且满足题目要求的：

原地修改