LeetCode 283. 移動零：雙指針原地算法

LeetCode 283. 移動零

題目描述

給定數組 nums，將所有 0 移至末尾，保持非零元素相對順序不變。要求原地操作，不拷貝額外數組。

範例

輸入：[0,1,0,3,12]
輸出：[1,3,12,0,0]

雙指針法（最優解）

維護指針 k 指向下一個非零元素應放置的位置。遍歷數組，遇非零元素置於 nums[k++]，遍歷結束後將剩餘位置填 0。

代碼實現

void moveZeroes(int* nums, int numsSize) {
    int k = 0;
    // 第一遍：將非零元素前移
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != 0) {
            nums[k++] = nums[i];
        }
    }
    // 第二遍：填充 0
    while (k < numsSize) {
        nums[k++] = 0;
    }
}

優化：單次遍歷交換法

若需嚴格單次遍歷，可用交換：

void moveZeroes(int* nums, int numsSize) {
    int k = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != 0) {
            int tmp = nums[k];
            nums[k] = nums[i];
            nums[i] = tmp;
            k++;
        }
    }
}

此法保證非零元素相對順序，且僅在必要時交換（i != k 時）。

複雜度分析

• 時間複雜度：O(n)，單次或雙次遍歷。
• 空間複雜度：O(1)，原地操作。

總結

移動零是雙指針技巧的入門題，核心思想是「收集非零元素」而非「移動零」。掌握「快慢指針」收集模式，可解決「移除元素、去重、分區」等同類原地數組問題。