[LeetCode解題攻略] 27. Remove Element

題目描述

給定一個整數數組 nums 和一個值 val，需要就地刪除數組中所有等於 val 的元素，並返回刪除後數組的新長度。

要求在 O(1) 額外空間內完成操作，並且元素的相對順序不需要保持一致。

範例 1：

輸入：

nums = [3, 2, 2, 3], val = 3

輸出：

2, nums = [2, 2, _, _]

解釋：函數返回的長度為 2，nums 的前兩個元素分別是 2，_ 表示不關心的數字。

範例 2：

輸入：

nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2

輸出：

5, nums = [0, 1, 3, 0, 4, _, _, _]

解釋：函數返回的長度為 5，nums 的前五個元素分別是 0、1、3、0 和 4。

解題思路

這題的核心在於：

1. 原地修改數組：不能使用額外數組存儲結果。
2. 快速處理重複出現的目標值 val。

可以使用雙指針技巧或直接遍歷進行操作。

解法一：雙指針法

思路

使用兩個指針：

• 快指針 (fast)：遍歷數組的每個元素。
• 慢指針 (slow)：表示新數組的最後一個有效位置。

當 nums[fast] != val 時，將 nums[fast] 的值複製到 nums[slow]，然後移動 slow。

如果 nums[fast] == val，跳過該元素。

詳細步驟

1. 初始化 slow = 0。
2. 使用 fast 遍歷數組：
3. • 如果 nums[fast] != val：
   • • 將 nums[fast] 的值複製到 nums[slow]。
     • 移動 slow 指針。
   • 否則，直接跳過。
3. 返回 slow，表示新數組的長度。

程式碼實現

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
        return slow

時間與空間複雜度

• 時間複雜度：O(n)，遍歷整個數組一次。
• 空間複雜度：O(1)，原地操作數組，無額外空間。

解法二：交換元素法

思路

當數組中目標值 val 很少時，上一種方法會多執行一些不必要的元素移動。

因此可以利用交換元素的方式：

• 當 nums[i] == val 時，將該元素與數組的最後一個元素交換，然後縮小數組的有效長度。

詳細步驟

1. 初始化 i = 0 和 n = len(nums)。
2. 遍歷數組：
3. • 如果 nums[i] == val：
   • • 將 nums[i] 和 nums[n - 1] 交換，並將有效長度 n 減 1。
     • 不移動 i，因為交換後的新值還需要檢查。
   • 如果 nums[i] != val，移動 i。
3. 返回 n，即新的有效長度。

程式碼實現

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        n = len(nums)
        i = 0
        while i < n:
            if nums[i] == val:
                nums[i], nums[n - 1] = nums[n - 1], nums[i]
                n -= 1
            else:
                i += 1
        return n

時間與空間複雜度

• 時間複雜度：O(n)，每個元素最多被檢查一次或交換一次。
• 空間複雜度：O(1)，原地操作數組。

總結

• 雙指針法 適合大多數情況，簡單易實現。
• 交換元素法 適合目標值 val 很少的情況，能減少不必要的操作。

希望這篇詳細教學能幫助大家更熟悉 LeetCode 第 27 題！