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)。