27. Remove Element

題目 / Problem

中文： 給定一個整數陣列 nums 和一個整數 val，請你原地移除 nums 中所有等於 val 的元素。元素的順序可以改變。然後回傳 nums 中不等於 val 的元素個數 k。

為了通過測試，你需要做到： - 修改 nums，使前 k 個元素為不等於 val 的元素，k 之後的元素不重要。 - 回傳 k。

English: Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Return the number k of elements in nums that are not equal to val.

To be accepted: - The first k slots of nums must hold all the elements that are not equal to val (any order). - Return k.

Constraints / 限制： - 0 <= nums.length <= 100 - 0 <= nums[i] <= 50 - 0 <= val <= 100

Example / 範例：

Input:  nums = [3,2,2,3], val = 3
Output: k = 2, nums = [2,2,_,_]

函式回傳 2，前兩個元素是 2, 2；底線 _ 代表什麼值都可以。 / The function returns 2; the first two elements are 2, 2; underscores are "don't care" slots.

名詞解釋 / Glossary

In-place / 原地修改：直接在原本的陣列上修改，不另外開一個新的陣列。空間複雜度通常是 O(1)。 / Modify the original array directly without allocating a new one; space is typically O(1).
Two pointers / 雙指針：使用兩個索引（指針）同時掃描陣列的技巧。這題用一個「讀指針」掃描每個元素，一個「寫指針」記錄下一個該寫入的位置。 / A technique that uses two indices to traverse an array simultaneously. Here one index reads every element and the other writes the keepers.
Pointer / 指標 (C)：在 C 語言中，int* 是一個儲存記憶體位址的變數，指向某個 int。nums[i] 與 *(nums + i) 等價。 / In C, int* stores the memory address of an int. nums[i] is equivalent to *(nums + i).
std::vector<int> (C++)：C++ 標準庫中的動態陣列，支援 v[i] 索引、v.size() 取長度。 / A dynamic array from the C++ STL; supports index v[i] and length v.size().
Reference & (C++)：vector<int>& nums 表示「傳參考」，函式內部對 nums 的修改會反映到呼叫端，不會複製整個 vector。 / vector<int>& nums passes by reference — modifications are visible to the caller and no copy is made.
Time complexity O(n) / 時間複雜度 O(n)：執行時間大致與輸入大小 n 成正比。 / Running time grows roughly proportional to input size n.

思路

這題要求「原地」刪除所有等於 val 的元素，並回傳剩下元素的個數 k。最直覺的暴力解是：每次遇到 val，就把後面的元素整個往前搬一格，但這樣每次搬移是 O(n)，總共 O(n²)，而且寫起來容易出錯。更聰明的做法是使用雙指針：用指針 i 從左到右掃描每個元素（讀指針），另一個指針 k 記錄「下一個該寫入的位置」（寫指針）。當 nums[i] != val 時，代表這個元素要保留，把它寫到 nums[k] 並把 k 往前推一格；當 nums[i] == val 時，直接跳過，k 不動。掃描結束後，nums[0..k-1] 就是所有不等於 val 的元素，而 k 正好是它們的個數。關鍵不變量（invariant）是：在每次迴圈開始時，nums[0..k-1] 永遠只包含已經確認保留的元素，因此寫入 nums[k] 不會覆蓋到還沒讀到的資料（因為 k <= i）。整個演算法只掃一次陣列，時間 O(n)、額外空間 O(1)。

The brute force is: every time we see val, shift all following elements one position left. That's O(n) per deletion and O(n²) overall — wasteful and error-prone. A much cleaner idea is the two-pointer pattern: use i as a read pointer that visits every index from left to right, and k as a write pointer that marks "where the next kept element should go." Whenever nums[i] != val, copy nums[i] into nums[k] and advance k; whenever nums[i] == val, skip it — don't advance k. After the single pass, nums[0..k-1] holds exactly the non-val elements and k is their count. The crucial invariant is that k <= i always, so writing to nums[k] never clobbers data we haven't read yet — the write pointer is never ahead of the read pointer. This runs in one linear pass: O(n) time and O(1) extra space.

逐步走查 / Walkthrough

Input: nums = [3,2,2,3], val = 3. Start with k = 0.

i	nums[i]	compare to val=3	action	k after	nums after
0	3	equal → skip	do nothing	0	[3,2,2,3]
1	2	not equal → keep	nums[0] = 2, k++	1	[2,2,2,3]
2	2	not equal → keep	nums[1] = 2, k++	2	[2,2,2,3]
3	3	equal → skip	do nothing	2	[2,2,2,3]

Loop ends. Return k = 2. The first two slots [2, 2] are the kept elements; slots 2 and 3 are "don't care" — LeetCode ignores them. / 迴圈結束，回傳 k = 2，前兩格 [2, 2] 就是答案，後兩格任意。

Solution — C

// 演算法：雙指針（快/慢指針）。i 讀每個元素，k 是下一個寫入位置。
// Algorithm: two pointers. i scans every element; k is the next write slot.
// 遇到不等於 val 的元素就寫到 nums[k] 並 k++；等於 val 就跳過。
// When nums[i] != val we copy it to nums[k] and advance k; otherwise we skip.
// 時間 O(n)，空間 O(1)。 / Time O(n), space O(1).

int removeElement(int* nums, int numsSize, int val) {
    // int* nums 是指向陣列第一個元素的指標；numsSize 是陣列長度。
    // int* nums points to the first element; numsSize is the array length.

    int k = 0;  // k 是下一個該寫入的位置，也是目前保留元素的個數。
                // k is the next write index, and also the count of kept elements so far.

    for (int i = 0; i < numsSize; i++) {  // i 從 0 掃到 numsSize-1。 / i scans 0..numsSize-1.
        if (nums[i] != val) {             // 只有不等於 val 的元素才要保留。
                                          // Only keep elements different from val.
            nums[k] = nums[i];            // 把保留的元素寫到位置 k。 / Write the keeper to slot k.
                                          // 因為 k <= i，不會覆蓋還沒讀到的資料。
                                          // Since k <= i, this never overwrites unread data.
            k++;                          // 寫指針往前推一格。 / Advance the write pointer.
        }
        // 如果 nums[i] == val，什麼都不做，i 繼續往前。
        // If nums[i] == val, do nothing; i moves on.
    }

    return k;  // k 就是保留下來的元素個數，也是 LeetCode 要的答案。
               // k is the number of kept elements — exactly what the judge wants.
}

Solution — C++

// 演算法與 C 版完全相同：雙指針一次掃描。
// Same algorithm as the C version: single-pass two pointers.
// 時間 O(n)、空間 O(1)。 / Time O(n), space O(1).

#include <vector>  // 引入 std::vector。 / Bring in std::vector.
using std::vector; // 讓我們可以直接寫 vector 而不是 std::vector。 / Alias for brevity.

class Solution {
public:
    // vector<int>& nums：以「參考」傳入，不複製整個 vector，函式內的修改對外可見。
    // vector<int>& nums: pass by reference — no copy, and changes are visible to the caller.
    int removeElement(vector<int>& nums, int val) {
        int k = 0;  // k = 下一個寫入位置 / k is the next write slot.

        // 範圍 for 迴圈：x 依序拿到 nums 的每個元素 (只讀)。
        // Range-based for loop: x takes each element of nums in order (read-only here).
        // 注意：我們只用 x 來讀取，寫回 nums 時還是用索引 k。
        // We use x only for reading; writing still uses index k.
        for (int x : nums) {
            if (x != val) {       // 保留不等於 val 的元素。 / Keep elements != val.
                nums[k] = x;      // 寫到 nums[k]。因為 k <= 當前讀的位置，安全。
                                  // Write to nums[k]; safe because k never overtakes the reader.
                k++;              // 寫指針前進。 / Advance the write pointer.
            }
        }

        return k;  // 回傳保留的元素個數。 / Return the count of kept elements.
    }
};

複雜度 / Complexity

Time / 時間: O(n) — n 是 nums 的長度。我們只用一個迴圈掃過每個元素一次，每次的比較與寫入都是 O(1)。 / n is the array length. A single pass visits each element once; each comparison and write is O(1).
Space / 空間: O(1) — 只用了 k 和 i 兩個整數變數，沒有額外的陣列或資料結構；修改是「原地」進行的。 / Only two integer variables k and i; no extra arrays — everything is done in-place.

Pitfalls & Edge Cases

空陣列 / Empty array (numsSize == 0)：迴圈條件 i < 0 立刻為假，直接回傳 k = 0，正確。 / The loop body never runs and we return k = 0. Correct — no special case needed.
全部都是 val / All elements equal val：k 從頭到尾都是 0，回傳 0，前 0 個元素（也就是沒有元素）符合要求。 / k stays at 0; we return 0, meaning "no kept elements" — matches the expected behavior.
完全沒有 val / No occurrences of val：每個位置都是 nums[k] = nums[i] 且 k == i，相當於把每個元素寫回原位，結果不變，回傳 numsSize。 / Every write is nums[k] = nums[i] with k == i — harmless self-copy. We return numsSize.
回傳值搞混 / Confusing return value：題目要的是「保留元素的個數 k」，不是「移除了幾個」。寫成 numsSize - k 會答錯。 / The problem asks for the count of kept elements, not removed. Returning numsSize - k is wrong.
寫指針超前讀指針？ / Could k ever exceed i?：不可能。k 只在 nums[i] != val 時才 ++，而 i 每一輪都 ++，所以 k <= i 恆成立；寫入 nums[k] 永遠不會蓋掉還沒讀到的資料。 / Impossible. k only advances when we find a keeper at i, and i advances every iteration, so k <= i always holds — writes never clobber unread data.
順序不保證 / Order not guaranteed by spec, but preserved here：本演算法實際上保留了非 val 元素的相對順序，這是一個 bonus，但題目並未要求。 / The algorithm happens to preserve the relative order of kept elements, but the problem does not require this.