@laigary.com~/interview/coding/27-remove-element.md$
$ cat ./coding/27-remove-element.md
[Coding]·2023-01-29·8 min read

27. Remove Element

27. Remove Element

把陣列裡所有等於 val 的元素移掉，回傳剩下的元素個數 k，並且讓前 k 格就是那些剩下的元素。和 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)，差別在實際的寫入量。能講出這個對比，比寫出其中任何一種解法都值錢。

解題方向

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

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 和 283. Move Zeroes 的骨架：

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 模板 的範圍內。

複雜度

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

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

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

--tags#Two Pointers
← cd ../codingcd ~