跳至内容

移除元素

LeetCode 27：用快慢指针将需要保留的元素依次写回数组前部。

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

题目：27. 移除元素

给定一个数组 nums 和一个值 val，原地移除所有等于 val 的元素，返回剩余元素的数量 k。

只需让数组的前 k 个位置保存需要保留的元素，后面的内容不参与判断。元素顺序可以改变，也不要求缩短数组本身的长度。

要求： 使用 O(1) 额外空间，在原数组上完成修改。

示例 1：

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

示例 2：

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

1. 移除过程

把不等于 val 的数依次写到数组前面，就完成了移除。 两个指针都从 0 开始：

  • fast：当前读取的下标，每轮前进一步。
  • slow：下一个写入的下标。遇到要保留的数，执行 nums[slow] = nums[fast] 后前进一步；遇到 val 则不动。最终 slow 就是保留数量。

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

第 1～2 轮：保留开头的 0、1

代码块 Text
1
2
3
4
5

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

0、1 都不等于 val，依次写回各自的原位置。每保留一个数，两个指针都前进一步；两轮后 slow = fast = 2，已保留 [0, 1]。

第 3～4 轮：跳过两个 2

代码块 Text
1
2
3
4
5

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

下标 2、3 处都是要移除的值，fast 从 2 走到 4。没有新增保留元素，slow 停在 2，等着下一个需要保留的数写到这里。

第 5 轮：将 3 写到下标 2

代码块 Text
1
2
3
4
5

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

fast = 4，读到的值是 3，需要保留；slow = 2，所以下一个数要写到下标 2。

执行 nums[2] = nums[4]：从右边取出 3，写入左边的位置。写完后，前面已保留 [0, 1, 3]，再更新 slow = 3、fast = 5。下标 4 处的旧 3 不用清空，只有前 slow 个位置算结果。

第 6 轮：将 0 写到下标 3

代码块 Text
1
2
3
4
5

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

执行 nums[3] = nums[5]，前面已保留 [0, 1, 3, 0]。更新 slow = 4、fast = 6。

第 7 轮：将 4 写到下标 4

代码块 Text
1
2
3
4
5

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

执行 nums[4] = nums[6]，前面已保留 [0, 1, 3, 0, 4]。更新 slow = 5、fast = 7。

第 8 轮：跳过末尾的 2

代码块 Text
1
2
3
4
5

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

2 == val，只把 fast 移到 8，遍历结束。返回 slow = 5，结果是前五个元素 [0, 1, 3, 0, 4]；下标 5～7 处的旧值无需清理。

fast 每轮前进，slow 只在保留时前进，所以每轮开始时都有 slow <= fast：写入只会覆盖当前或已经读过的位置，不会破坏尚未读取的元素。

2. Python 实现

while 判断还有没有元素可读，if 判断读到的元素要不要保留。

每轮都会读取 nums[fast]，所以循环条件必须保证这个下标存在。本例 len(nums) = 8，有效下标是 0～7：

  • fast = 7：还有最后一个元素要检查，继续循环。
  • fast = 8：已经读完，结束循环；此时再访问 nums[8] 就会越界。

下面是遍历结束时的坐标图。竖线右侧已经在数组外，8 标记的是停止位置，没有对应的元素。

代码块 Text
1
2
3
4
5

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

因此写 fast < len(nums)，也可以写成等价的 fast <= len(nums) - 1。覆盖元素不会缩短列表，len(nums) 仍为 8；返回的 slow = 5 表示结果占前五个位置。

如果误写成 fast < len(nums) - 1，就会漏读最后一个元素。本例末尾恰好是要跳过的 2，结果可能碰巧一样，不能据此判断循环条件正确。

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

def remove_element(nums, val):
    fast, slow = 0, 0
    while fast < len(nums):  # fast 是下标，最大只能读到 len(nums) - 1
        if nums[fast] != val:  # 当前元素需要保留，才写入结果
            nums[slow] = nums[fast]
            slow += 1
        fast += 1  # 无论保留还是跳过，都要继续检查下一个元素
    return slow  # 已保留的元素数量


nums = [0, 1, 2, 2, 3, 0, 4, 2]
length = remove_element(nums, val=2)
print(length)
print(nums[:length])
运行结果 Text
1
2

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

3. 复杂度

设 n 为输入数组的长度。

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

评论

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

阅读到这里时加载评论。