Intuition #

這題的核心限制是 原地 (in-place) 修改陣列與 O(1) 額外空間。 我們不能建立一個新陣列來存結果，必須直接覆蓋原本陣列不需要的元素。這類「在陣列中篩選/移動元素」的問題， 雙指針 (Two Pointers) 是最標準的解法：一個指針負責讀取 (Reader)，一個指針負責寫入 (Writer)。

我們需要維護一個邊界 k，使得 nums[0...k-1] 都是我們想要的元素（即不等於 val 的數字）。

Approaches #

1: Two Pointers (Standard) #

• 概念:
  • 定義一個 writer 指針（也可以視為計數器 k），初始指向 0
  • 用另一個 reader 指針（迴圈變數 i）遍歷整個陣列
  • 當 nums[i] 不是我們要刪除的目標 val 時，將其複製到 nums[writer] 的位置，並將 writer 向前移動
  • 如果 nums[i] 是 val，則跳過，不做任何動作
• 時間複雜度: O(n) - 我們遍歷陣列一次
• 空間複雜度: O(1) - 原地修改

class Solution {
    fun removeElement(nums: IntArray, `val`: Int): Int {
        var writer = 0

        for (reader in nums.indices) {
            // 如果當前數字不是要刪除的目標，就把它保留下來
            if (nums[reader] != `val`) {
                nums[writer] = nums[reader]
                writer++
            }
        }

        // writer 最後的位置就是新陣列的長度
        return writer
    }
}

⭐2: Two Pointers with Swapping (Optimization for Rare Removal) #

• 概念:
  • 如果需要刪除的元素 val 在陣列中非常稀少（例如陣列長度 1000，只有 1 個要刪），標準解法仍會執行大量不必要的賦值操作（把前面元素往左移）
  • 我們可以改用雙向指針。當左指針 i 遇到要刪除的val時，直接將陣列最後一個元素搬來覆蓋它，然後將陣列有效長度減一
  • 這樣可以減少賦值操作的次數
• 時間複雜度: O(n) - 左右指針總共遍歷n個元素
• 空間複雜度: O(1)

class Solution {
    fun removeElement(nums: IntArray, `val`: Int): Int {
        var i = 0
        var n = nums.size

        while (i < n) {
            if (nums[i] == `val`) {
                // 發現目標，直接用最後一個元素覆蓋它
                nums[i] = nums[n - 1]
                // 陣列有效長度縮短
                n--
                // 注意：這裡不執行 i++，因為換過來的那個新元素可能也是 val，需要下一輪再次檢查
            } else {
                i++
            }
        }
        return n
    }
}

這方法的代價是改變了元素相對順序。但題目說明 “The order of the elements may be changed”，所以是允許的。

3: Filter Approach (Conceptual) #

• 概念: 在實際工程開發中（非 LeetCode 限制環境），我們通常會優先用 Kotlin 標準庫提供的函數，以提高可讀性
• 限制: 這不符合題目的 O(1) 空間複雜度要求，因為 filter 會建立一個新 List。這裡列出僅供參考 Kotlin 的寫法

// 這是 "Functional" 風格，但在 LeetCode 會因為沒有原地修改陣列而判錯 (或是記憶體較高)
fun removeElementExample(nums: IntArray, `val`: Int): List<Int> {
    return nums.filter { it != `val` }
}

🔑Takeaways #

• 雙指針模式: 當需要在陣列中「原地」移除或篩選元素時，Reader/Writer 雙指針模式是基本功
• 賦值優化: 如果題目允許改變順序，且目標元素很少，用「交換移除法 (Swap Removal)」可以減少寫入次數
• 原地操作: 永遠要注意題目是否要求 In-place，這通常意味著不能使用 filter、map 等產生新集合的函數