題目

題目翻譯

給定一個數組nums和一個值val，你需要原地移除所有數值等於val的元素，返回移除後數組的新長度。
不要使用額外的數組空間，你必須在原地修改輸入數組並使用O（1）額外空間的條件下完成。
元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。

解題思路

這題要求從陣列 nums 中移除所有等於 val 的元素，並返回移除後的陣列長度。同時要就地修改陣列，也就是說空間複雜度應該為 O(1)。要求的步驟如下：

1. 遍歷陣列：我們需要遍歷陣列，並檢查每個元素是否等於 val。
2. 移除匹配的元素：如果元素等於 val，則將其從陣列中移除，並更新陣列的大小。
3. 保持不匹配的元素：如果元素不等於 val，則繼續遍歷下一個元素。
4. 返回新陣列的長度：最後返回移除指定元素後的陣列大小。

問題點

在原始程式碼中，每次找到要移除的元素時，使用 erase 方法刪除，這會使後面的元素全部向前移動，導致時間複雜度變高。erase 是 O(n) 操作，當每次都需要移動元素時，最壞情況下的時間複雜度會變成 O(n^2)。這種方法在數據量大的情況下會變得非常低效。

改進版本程式碼

為了避免多次移動元素，我們可以使用雙指針方法（類似「移動零」的解法）來進行優化。只需要一次遍歷即可完成所有操作，並且時間複雜度可以保持在 O(n)。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int index = 0;  // 用於記錄非 val 元素的索引位置
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != val) {
                nums[index] = nums[i];  // 將非 val 的元素移到前面
                ++index;  // 更新位置
            }
        }
        return index;  // 返回移除後的陣列長度
    }
};

解題步驟

1. 雙指針法：

   • 使用一個指針 index 來追蹤不等於 val 的元素應該被放置的位置。
   • 使用另一個指針 i 來遍歷整個陣列。
   • 每當發現元素不等於 val 時，將該元素移動到 index 位置，並將 index 向前移動一位。

2. 覆蓋原來的數組：

   • 將不等於 val 的元素覆蓋在前面，這樣陣列的前 index 位會存放不等於 val 的元素。

3. 返回結果：

   • 最後，index 的值就是移除指定元素後的陣列長度。

這種方法時間複雜度為 O(n)，因為每個元素只被遍歷一次，並且空間複雜度為 O(1)，滿足題目的要求。