27. 移除元素

快慢指針法

算法思路

• 使用雙指針（fast和slow）遍歷數組。
  • fast指針遍歷每一個元素。
  • slow指針指向下一個將被保留的位置。
• 如果nums[fast] != val，就把nums[fast]賦值到nums[slow]，并將slow向前移動一位。
• 遍歷結束后，slow的值就是新數組的長度，數組前slow個元素即為移除指定元素后的結果。

注意：

• 題目要求原地操作，不能使用額外數組。
• 不關心原數組后面剩余的元素。

#快慢雙指針法
class Solution:def removeElement(self, nums: List[int], val: int) -> int:fast = slow = 0size = len(nums)while fast < size:if nums[fast] != val:nums[slow] = nums[fast]slow += 1fast += 1return slow

時間復雜度

• O(n)，n為數組長度。每個元素最多被訪問兩次（一次被fast讀，一次被slow寫）。

---

空間復雜度

• O(1)，只用了常數級別的額外空間。

暴力法

算法思路

• 用變量i遍歷數組，l記錄當前數組有效長度。
• 每當nums[i] == val，就從i+1到l-1的所有元素整體向前移動一位（覆蓋掉nums[i]）。
• 有效長度l減1，i回退1（這樣下一輪循環會檢查移過來的新元素）。
• 遍歷直到i == l。

#（版本二）暴力法
class Solution:def removeElement(self, nums: List[int], val: int) -> int:i, l = 0, len(nums)while i < l:if nums[i] == val: # 找到等于目標值的節點for j in range(i+1, l): # 移除該元素，并將后面元素向前平移nums[j - 1] = nums[j]l -= 1i -= 1i += 1return l

時間復雜度

• 最壞情況下：每遇到一個等于val的元素，就要把后面所有元素向前平移一次。
• 假設數組長度為n，且所有元素都等于val，每次移動n-1, n-2, ..., 1次，總操作次數為O(n^2)。
• 所以時間復雜度為O(n^2)。

---

空間復雜度

• 沒有申請額外數組，只用了常數個變量。
• 空間復雜度為O(1)。