leetcode中如何解決移除元素問題

# LeetCode中如何解決移除元素問題

## 引言

在算法學習與面試準備過程中，LeetCode是一個不可或缺的平臺。其中，"移除元素"（Remove Element）作為數組操作類的基礎題目，不僅考察了對數組結構的理解，更是雙指針技巧的經典應用場景。本文將深入剖析該問題的多種解法，從暴力法到優化策略，逐步引導讀者掌握解題思路與編碼技巧。

---

## 問題描述

**題目編號**：27. Remove Element  
**難度**：Easy  
**鏈接**：https://leetcode.com/problems/remove-element/

給定一個整數數組 `nums` 和一個整數 `val`，要求原地移除所有數值等于 `val` 的元素，并返回移除后數組的新長度。必須使用 O(1) 的額外空間（即原地修改輸入數組），且可以忽略新長度后面的元素。

**示例**：
```python
輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2,...]  # 新長度后的元素不重要

輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,3,0,4,...]

解法一：暴力解法（不推薦）

思路分析

最直觀的方法是遍歷數組，每當遇到目標值 val 時，將其后的所有元素向前移動一位。這種方法雖然簡單，但時間復雜度較高。

代碼實現

def removeElement(nums, val):
    i = 0
    length = len(nums)
    while i < length:
        if nums[i] == val:
            # 將后續元素整體前移
            for j in range(i + 1, length):
                nums[j - 1] = nums[j]
            length -= 1  # 數組長度減1
            i -= 1       # 因為前移后當前位置可能有新元素需要檢查
        i += 1
    return length

復雜度分析

• 時間復雜度：O(n2)
  嵌套循環導致最壞情況下需遍歷 n2 次。
• 空間復雜度：O(1)
  僅使用常數級額外空間。

解法二：雙指針（快慢指針）

思路分析

通過快慢指針（Fast-Slow Pointer）優化： - 慢指針 slow：指向下一個待填充的位置。 - 快指針 fast：遍歷數組，尋找非 val 元素。

當 fast 遇到非 val 值時，將其復制到 slow 位置，并移動兩個指針；否則僅移動 fast。

代碼實現

def removeElement(nums, val):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return slow

復雜度分析

• 時間復雜度：O(n)
  單次遍歷數組。
• 空間復雜度：O(1)
  僅使用兩個指針變量。

示例演示

以 nums = [0,1,2,2,3,0,4,2], val = 2 為例：

fast=0: nums[0]=0 ≠2 → nums[0]=0, slow=1
fast=1: nums[1]=1 ≠2 → nums[1]=1, slow=2
fast=2: nums[2]=2 → 跳過
fast=3: nums[3]=2 → 跳過
fast=4: nums[4]=3 ≠2 → nums[2]=3, slow=3
...
最終返回 slow=5，nums=[0,1,3,0,4,...]

解法三：雙指針優化（前后指針）

適用場景

當待移除元素較少時（如 val 只出現在數組開頭），解法二中仍會進行不必要的復制。此時可采用前后指針（頭尾交換法）減少操作次數。

思路分析

• 左指針 left：從數組頭部開始，尋找等于 val 的元素。
• 右指針 right：從數組尾部開始，尋找不等于 val 的元素。
• 交換兩者值，并移動指針。

代碼實現

def removeElement(nums, val):
    left, right = 0, len(nums) - 1
    while left <= right:
        if nums[left] == val:
            nums[left] = nums[right]  # 交換可簡化為直接覆蓋
            right -= 1
        else:
            left += 1
    return left

復雜度分析

• 時間復雜度：O(n)
  最壞情況下遍歷整個數組一次。
• 空間復雜度：O(1)
  僅使用常數空間。

注意事項

• 此方法會改變元素原始順序。
• 適合對元素順序無要求的場景。

解法對比與選擇

邊界條件與測試用例

常見邊界情況

1. 空數組 []。
2. 數組全為 val，如 [2,2,2], val=2。
3. 數組無 val，如 [1,3,4], val=2。
4. val 在首尾或連續出現。

測試用例示例

assert removeElement([], 3) == 0
assert removeElement([2,2,2], 2) == 0
assert removeElement([1,3,4], 2) == 3
assert removeElement([3,1,3,3,2], 3) == 2

擴展思考

相似題目

1. 26. 刪除有序數組中的重復項：快慢指針的變體。
2. 283. 移動零：將零移到末尾，等價于移除零后補零。
3. 844. 比較含退格的字符串：雙指針模擬退格操作。

實際應用

• 內存清理：標記刪除無效數據后壓縮存儲空間。
• 數據預處理：過濾特定值的記錄。

總結

“移除元素”問題通過雙指針技巧將時間復雜度從 O(n2) 優化至 O(n)，是算法學習中”以空間換時間”思想的經典體現。掌握快慢指針與前后指針的適用場景，能有效解決同類數組操作問題。建議讀者在理解基礎上，嘗試自行編寫代碼并通過LeetCode測試，加深對指針移動的理解。

”`

文章字數：約2250字（含代碼與格式）
提示：實際使用時可根據需要調整代碼注釋或示例的詳細程度。