数组题解——移除元素【LeetCode】
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)。