LeetCode 283: Move Zeroes

看到這題第一個想法是想說就一直交換，直到零都被交換到後面，後來想到應該可以「把所有非零的元素抓出來，剩下補零就好了」。

題目

題目連結：LeetCode 283. Move Zeroes

給定一個整數陣列 nums，將所有的 0 移到陣列的最後面，同時保持非零元素的相對順序。必須 原地 操作，不能複製陣列。

Example:

• Input: nums = [0, 1, 0, 3, 12]
• Output: [1, 3, 12, 0, 0]

快慢指標的想法

兩個指標，各有各的用途：

• read：負責掃描整個陣列，每個元素都會走過一次。
• write：只關心「下一個非零數字要放哪」，每次有非零數字進來，就把它放到 write 的位置，然後 write 往前一步。

這樣跑完一遍，所有非零數字都已經照原順序塞到陣列前段了，write 停下來的位置之後全部補 0 就完成了。

write 永遠不會跑到 read 前面，因為 write 只有在真的寫入時才加一，所以覆寫不會蓋到還沒讀的資料。

走一遍範例

用 nums = [0, 1, 0, 3, 12] 跑一遍：

Table 1: 實際走訪過程

第一個 loop 結束後，write = 3，代表前三個位置已經放好了非零數字。

接著從 write 到結尾補 0：

Table 2: 補零過程

指標沒定義清楚的陷阱

一開始容易想成「兩個指標一起動，互相交換」，但這樣容易搞混，不知道誰負責掃描、誰負責放東西。

把 read 和 write 的職責分開想清楚，邏輯就簡單很多：read 只管往前走，write 只管有非零就收下來。

程式碼

from typing import List

def moveZeroes(nums: List[int]) -> None:
    write = 0  # 下一個非零要寫入的位置

    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write] = nums[read]
            write += 1

    # 剩下的位置補 0
    for i in range(write, len(nums)):
        nums[i] = 0

複雜度

• 時間複雜度：$O(n)$。read 走過陣列一次，補零最多再走一次。
• 空間複雜度：$O(1)$。只用了 write、read 兩個常數額外變數。

小結

這題的核心是「把收集有效值和補填空位拆成兩步」，想清楚之後實作就非常直覺。

一樣的 Two Pointers 原地覆寫技巧在 27. Remove Element 和 443. String Compression 也用得到，三題可以一起練習。