Leetcode27.移除元素
目录
问题描述
算法思路
代码实现
示例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)，只使用常数级别的额外空间