LeetCode Remove Element：三種原地移除目標值算法對比與最佳實踐

題目要求

給定陣列 nums 與值 val，原地移除所有等於 val 的元素，返回新長度。元素順序可改變，超出新長度部分內容不限。

方案一：雙指針對撞（前後掃描交換）

思路：left 從前找目標值，right 從後找非目標值，交換並縮小區間。
優點：交換次數最少（最多 min(目標個數, 非目標個數) 次）。
缺點：順序完全打亂。

int removeElement(vector& nums, int val) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        if (nums[left] != val) ++left;
        else if (nums[right] == val) --right;
        else nums[left++] = nums[right--];  // 覆蓋而非 swap，因右側將被捨棄
    }
    return right + 1;  // 或 left
}

方案二：單指針 + 長度縮減（Discuss 高票解）

思路：維護有效長度 n，i 從 0 掃描。遇到目標值，用尾端元素 nums[--n] 覆蓋 nums[i]，i 不動（因新覆蓋元素未檢查）。
優點：程式碼極簡，無需雙指針。
缺點：若尾端連續是目標值，會重複覆蓋同位置。

int removeElement(vector& nums, int val) {
    int n = nums.size();
    for (int i = 0; i < n; ) {
        if (nums[i] == val) nums[i] = nums[--n];
        else ++i;
    }
    return n;
}

方案三：快慢指針保序（覆蓋法）

思路：slow 指向下一個放置非目標值的位置，fast 掃描全陣列。非目標值複製到 slow 並 slow++。
優點：保持相對順序。
缺點：需移動所有非目標元素，若目標在開頭則全陣列搬移。

int removeElement(vector& nums, int val) {
    int slow = 0;
    for (int fast = 0; fast < nums.size(); ++fast)
        if (nums[fast] != val) nums[slow++] = nums[fast];
    return slow;
}

效能對比總結

最佳選擇建議

• 面試/競程首選方案二：程式碼最短、邏輯清晰、無順序要求時最優。
• 需保序場景：唯有方案三（如後續需二分搜尋、輸出有序結果）。
• 寫入成本極高（如 Flash 記憶體）：方案一寫入次數最少。

Java/Python 實作參考

// Java 方案二
public int removeElement(int[] nums, int val) {
    int n = nums.length;
    for (int i = 0; i < n; ) {
        if (nums[i] == val) nums[i] = nums[--n];
        else i++;
    }
    return n;
}

# Python 方案三（列表推導式最簡潔，但非原地）
def removeElement(nums, val):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return slow