跳至内容

删除有序数组中的重复项

LeetCode 26：比较当前元素与最后一个已保留元素，原地完成有序数组去重。

LeetCode 26 简单 数组
发布于 更新于 约 3 分钟阅读 浏览 — 次
  • 数组
  • 双指针
  • Python

题目：26. 删除有序数组中的重复项

给定一个非空、按非递减顺序排列的数组 nums（后一个数不小于前一个数），原地去重，使每个数只保留一次，返回唯一元素的数量 k。

保持元素的相对顺序，让数组的前 k 个位置保存去重结果，后面的内容可以忽略。要求使用 O(1) 额外空间。

示例 1：

  • 输入： nums = [1, 1, 2]
  • 返回： 2
  • 修改后： 前两个元素为 [1, 2]。

示例 2：

  • 输入： nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
  • 返回： 5
  • 修改后： 前五个元素为 [0, 1, 2, 3, 4]。

1. 去重过程

数组有序，相同的数会连续出现。当前数与最后一个已保留的数相等，就跳过；不同，就追加到结果后面。 初始保留 nums[0]，两个指针都从 0 开始：

  • fast：当前读取的下标，每轮前进一步。
  • slow：最后一个已保留元素的下标。

下面用示例 2 演示。图中 index 是下标、value 是值，箭头标出每次操作前的指针位置。

第 1～2 轮：跳过相同的 0

代码块 Text
1
2
3
4
5

index:  0   1   2   3   4   5   6   7   8   9
value:  0   0   1   1   1   2   2   3   3   4
        ●───●───●───●───●───●───●───●───●───●
fast:   ↑
slow:   ↑

第一次将 nums[0] 与自身比较，第二次读到的仍是 0，都不写入。两轮后 fast = 2、slow = 0，已保留 [0]。

第 3 轮：追加新值 1

代码块 Text
1
2
3
4
5

index:  0   1   2   3   4   5   6   7   8   9
value:  0   0   1   1   1   2   2   3   3   4
        ●───●───●───●───●───●───●───●───●───●
fast:           ↑
slow:   ↑

1 与已保留的 0 不同，要放到它后面：先将 slow 从 0 移到 1，再执行 nums[1] = nums[2]。

这轮结束时 slow = 1、fast = 3，已保留 [0, 1]。

第 4～5 轮：跳过重复的 1

代码块 Text
1
2
3
4
5

index:  0   1   2   3   4   5   6   7   8   9
value:  0   1   1   1   1   2   2   3   3   4
        ●───●───●───●───●───●───●───●───●───●
fast:               ↑
slow:       ↑

fast 连续读到两个重复的 1，slow = 1 不动，fast 移到 5。

第 6～7 轮：追加 2，跳过重复的 2

代码块 Text
1
2
3
4
5

index:  0   1   2   3   4   5   6   7   8   9
value:  0   1   1   1   1   2   2   3   3   4
        ●───●───●───●───●───●───●───●───●───●
fast:                       ↑
slow:       ↑

将 2 写入下标 2，后一个 2 跳过。两轮后 slow = 2、fast = 7。

第 8～9 轮：追加 3，跳过重复的 3

代码块 Text
1
2
3
4
5

index:  0   1   2   3   4   5   6   7   8   9
value:  0   1   2   1   1   2   2   3   3   4
        ●───●───●───●───●───●───●───●───●───●
fast:                               ↑
slow:           ↑

将 3 写入下标 3，后一个 3 跳过。两轮后 slow = 3、fast = 9。

第 10 轮：追加最后的 4

代码块 Text
1
2
3
4
5

index:  0   1   2   3   4   5   6   7   8   9
value:  0   1   2   3   1   2   2   3   3   4
        ●───●───●───●───●───●───●───●───●───●
fast:                                       ↑
slow:               ↑

将 4 写入下标 4，随后 fast 移到 10，遍历结束。

结果占下标 0～4，共五个位置，保存 [0, 1, 2, 3, 4]。slow = 4 是最后一个已保留元素的下标，返回的长度是 slow + 1 = 5。

2. Python 实现

用 fast <= len(nums) - 1 遍历到最后一个元素，等价写法是 fast < len(nums)。

发现新值时，slow 在 fast 左侧，加 1 后也不会超过 fast，因此写入不会覆盖尚未读取的元素。

代码块 Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def remove_repeat_element(nums):
    slow, fast = 0, 0  # 首个元素已保留，slow 指向它
    while fast <= len(nums) - 1:
        if nums[fast] != nums[slow]:  # 与最后一个已保留元素不同，才追加
            slow += 1  # 先移动到下一格，保留 slow 原来指向的元素
            nums[slow] = nums[fast]
        fast += 1  # 无论是否重复，都继续读取下一个元素
    return slow + 1  # slow 是最后一个已保留元素的下标，长度需要加 1


nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k = remove_repeat_element(nums)
print(k)
print(nums[:k])
运行结果 Text
1
2

# 5
# [0, 1, 2, 3, 4]

3. 复杂度

设 n 为输入数组的长度。

  • 时间复杂度：O(n)，fast 从左到右遍历一次，每个元素只检查一次。
  • 额外空间复杂度：O(1)，原地覆盖元素，只维护两个下标变量。

评论

使用 GitHub 登录后参与讨论，评论将公开保存在 GitHub。

阅读到这里时加载评论。