目录

问题描述

算法思路

代码实现

示例1

双指针法执行过程

最终结果

复杂度分析

问题描述

给定一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

算法思路

使用双指针法 来解决这个问题：

1. 1.
慢指针(i) ：指向下一个不等于val的元素应该放置的位置
2. 2.
快指针(j) ：遍历整个数组，检查每个元素
算法步骤
1. 1.
初始化慢指针i为0
2. 2.
用快指针j遍历数组
3. 3.
如果nums[j]不等于val，则将nums[j]的值赋给nums[i]，然后i自增
4. 4.
遍历结束后，i的值就是数组中不等于val的元素数量

代码实现

class Solution(object): def removeElement(self, nums, val): # 使用双指针法 # i: 慢指针，指向下一个不等于val的元素应该放置的位置 # j: 快指针，遍历整个数组 i = 0 for j in range(len(nums)): if nums[j] != val: nums[i] = nums[j] i += 1 return i

示例1

输入：nums = [3,2,2,3], val = 3

输出：2, 数组的前两个元素为 [2,2]

双指针法执行过程

使用双指针法解决这个问题：慢指针 i 用于记录结果数组的位置，快指针 j 用于遍历原数组。

初始化

慢指针 i = 0，快指针 j = 0

nums = [3, 2, 2, 3] i = 0, j = 0

第1步

快指针 j 指向 nums[0] = 3，等于 val = 3，跳过此元素

nums = [3, 2, 2, 3] i = 0, j = 0

慢指针 i 保持不变，快指针 j 准备移动到下一个位置

第2步

快指针 j 指向 nums[1] = 2，不等于 val = 3，将 nums[1] 赋值给 nums[i]

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

i = 0 → 1, j = 1

慢指针 i 自增为 1，快指针 j 准备移动到下一个位置

第3步

快指针 j 指向 nums[2] = 2，不等于 val = 3，将 nums[2] 赋值给 nums[i]

nums = [2, 2, 2, 3] nums[1] = nums[2] = 2

i = 1 → 2, j = 2

慢指针 i 自增为 2，快指针 j 准备移动到下一个位置

第4步

快指针 j 指向 nums[3] = 3，等于 val = 3，跳过此元素

nums = [2, 2, 2, 3] i = 2, j = 3

慢指针 i 保持不变为 2，快指针 j 准备移动到下一个位置

第5步

快指针 j 已经遍历完整个数组，算法执行完毕

nums = [2, 2, 2, 3] i = 2, j = 3

最终结果

慢指针 i 的值为 2，表示数组中有 2 个不等于 val 的元素

数组前 i 个元素 [2, 2] 即为移除所有 val 后的结果

返回值：2

结果数组：[2, 2, 2, 3]（前2个元素为有效结果）

复杂度分析

时间复杂度：O(n)，只遍历数组一次

空间复杂度：O(1)，只使用常数级别的额外空间