---
title: "27. Remove Element"
url: "https://laigary.com/interview/coding/27-remove-element"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-28"
tags: ["Two Pointers"]
---

# 27. Remove Element

[27\. Remove Element](https://leetcode.com/problems/remove-element/)

把陣列裡所有等於 `val` 的元素移掉，回傳剩下的元素個數 `k`，並且讓前 `k` 格就是那些剩下的元素。和 [26. Remove Duplicates from Sorted Array](/interview/coding/26-remove-duplicates-from-sorted-array) 一樣是「回傳值 + 原地副作用」的組合。

## 思路

這題有一句話決定了一切，藏在敘述裡很容易漏掉：

> **The order of the elements may be changed.**

剩下的元素**順序不拘**。這就是「把 `val` 跟尾巴的值交換」這個做法的許可證 —— 我不需要保持任何相對順序，所以不要的元素可以直接丟到後面去，用尾巴的值填補它的位置。

拿旁邊兩題對比就很清楚為什麼只有這題能這樣做：

| 題目 | 順序限制 | 能不能跟尾端交換 |
|---|---|---|
| 26 Remove Duplicates | 必須維持排序 | 不行 |
| 283 Move Zeroes | 非零元素要維持相對順序 | 不行 |
| **27 Remove Element** | **無** | **可以** |

所以要從兩個方向看：

1. **右指針**負責從尾端往左找，找到第一個不等於 `val` 的值 —— 那是可以拿來填補的材料。如果尾端本身就是 `val`，它沒有用，往左退。
2. **左指針**往右走，一遇到 `val` 就跟右指針的值交換，把 `val` 丟到後面。

還有一個值得在面試講出來的權衡：**這個做法只在遇到 `val` 時才寫入**，而快慢指針是每個「保留下來的元素」都要寫一次。所以兩者的寫入量剛好是反過來的 —— 對撞交換正比於「要移除的個數」，快慢指針正比於「要保留的個數」。

也就是說：**要移除的東西很少時選對撞交換，很多時選快慢指針。** 兩者都是 $O(n)$，差別在實際的寫入量。能講出這個對比，比寫出其中任何一種解法都值錢。

## 解題方向

```python
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:
            while nums[right] == val and left < right:
                right -= 1
            if nums[left] == val:
                nums[left], nums[right] = nums[right], nums[left]
            left += 1

        return sum([1 for num in nums if num != val])
```

內層那個 `while` 的 `left < right` 條件不能省。整個陣列都是 `val` 的時候（例如 `[2, 2, 2]`），`right` 會一路往左退，沒有這個守衛它就會退過 `left` 變成負索引。加上它之後，兩個指針最壞情況就是在中間相遇然後停住。

也因為迴圈條件是 `left < right`（而不是 `<=`），當兩者相遇時那一格不會被檢查 —— 所以最後不能直接用指針位置當答案，這也是下面那行 `sum(...)` 的來由。

## 補充

**那行 `sum(...)` 其實可以省掉。** 它多掃了一整遍陣列（總共兩趟，複雜度不變但沒必要），而指針本身已經帶著答案。換一種寫法就能直接回傳：

```python
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i, n = 0, len(nums)
        while i < n:
            if nums[i] == val:
                nums[i] = nums[n - 1]   # 用尾巴的值蓋掉，尾巴縮短
                n -= 1                  # i 不前進，換過來的值還沒檢查
            else:
                i += 1
        return n
```

這裡 `n` 同時扮演「有效區間的長度」和「答案」，所以掃完直接回傳。要注意 `nums[i] == val` 時 `i` **不能前進** —— 從尾巴換過來的那個值還沒被檢查過，它也可能是 `val`。

**快慢指針的版本**，也就是 [26](/interview/coding/26-remove-duplicates-from-sorted-array) 和 [283. Move Zeroes](/interview/coding/283-move-zeroes) 的骨架：

```python
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
        return slow
```

這版比較短也比較好記，而且回傳 `slow` 就是答案。代價是寫入次數比較多（見上面的表）—— 要移除的元素很少時，換成跟尾端交換可以少寫很多次。

三種寫法都在 [Two Pointers 模板](/interview/coding/two-pointers-template) 的範圍內。

## 複雜度

三種寫法都是同一組複雜度：

- 時間 $O(n)$ — 每一格最多被 `left` / `right`（或 `i`）碰過一次
- 空間 $O(1)$ — 只用索引變數，原地改寫

其中 $n$ 是陣列長度。第一種寫法最後多一趟 `sum(...)`，是兩趟掃描，但仍然是 $O(n)$。