您好,登录后才能下订单哦!
# LeetCode中如何解决移除元素问题
## 引言
在算法学习与面试准备过程中,LeetCode是一个不可或缺的平台。其中,"移除元素"(Remove Element)作为数组操作类的基础题目,不仅考察了对数组结构的理解,更是双指针技巧的经典应用场景。本文将深入剖析该问题的多种解法,从暴力法到优化策略,逐步引导读者掌握解题思路与编码技巧。
---
## 问题描述
**题目编号**:27. Remove Element
**难度**:Easy
**链接**:https://leetcode.com/problems/remove-element/
给定一个整数数组 `nums` 和一个整数 `val`,要求原地移除所有数值等于 `val` 的元素,并返回移除后数组的新长度。必须使用 O(1) 的额外空间(即原地修改输入数组),且可以忽略新长度后面的元素。
**示例**:
```python
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2,...] # 新长度后的元素不重要
输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,3,0,4,...]
最直观的方法是遍历数组,每当遇到目标值 val
时,将其后的所有元素向前移动一位。这种方法虽然简单,但时间复杂度较高。
def removeElement(nums, val):
i = 0
length = len(nums)
while i < length:
if nums[i] == val:
# 将后续元素整体前移
for j in range(i + 1, length):
nums[j - 1] = nums[j]
length -= 1 # 数组长度减1
i -= 1 # 因为前移后当前位置可能有新元素需要检查
i += 1
return length
通过快慢指针(Fast-Slow Pointer)优化:
- 慢指针 slow
:指向下一个待填充的位置。
- 快指针 fast
:遍历数组,寻找非 val
元素。
当 fast
遇到非 val
值时,将其复制到 slow
位置,并移动两个指针;否则仅移动 fast
。
def removeElement(nums, val):
slow = 0
for fast in range(len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow
以 nums = [0,1,2,2,3,0,4,2], val = 2
为例:
fast=0: nums[0]=0 ≠2 → nums[0]=0, slow=1
fast=1: nums[1]=1 ≠2 → nums[1]=1, slow=2
fast=2: nums[2]=2 → 跳过
fast=3: nums[3]=2 → 跳过
fast=4: nums[4]=3 ≠2 → nums[2]=3, slow=3
...
最终返回 slow=5,nums=[0,1,3,0,4,...]
当待移除元素较少时(如 val
只出现在数组开头),解法二中仍会进行不必要的复制。此时可采用前后指针(头尾交换法)减少操作次数。
left
:从数组头部开始,寻找等于 val
的元素。right
:从数组尾部开始,寻找不等于 val
的元素。def removeElement(nums, val):
left, right = 0, len(nums) - 1
while left <= right:
if nums[left] == val:
nums[left] = nums[right] # 交换可简化为直接覆盖
right -= 1
else:
left += 1
return left
解法 | 时间复杂度 | 空间复杂度 | 是否保持顺序 | 适用场景 |
---|---|---|---|---|
暴力法 | O(n²) | O(1) | 是 | 教学理解,实际不推荐 |
快慢双指针 | O(n) | O(1) | 是 | 通用最优解 |
前后双指针 | O(n) | O(1) | 否 | val 较少且无需保序时 |
[]
。val
,如 [2,2,2], val=2
。val
,如 [1,3,4], val=2
。val
在首尾或连续出现。assert removeElement([], 3) == 0
assert removeElement([2,2,2], 2) == 0
assert removeElement([1,3,4], 2) == 3
assert removeElement([3,1,3,3,2], 3) == 2
“移除元素”问题通过双指针技巧将时间复杂度从 O(n²) 优化至 O(n),是算法学习中”以空间换时间”思想的经典体现。掌握快慢指针与前后指针的适用场景,能有效解决同类数组操作问题。建议读者在理解基础上,尝试自行编写代码并通过LeetCode测试,加深对指针移动的理解。
”`
文章字数:约2250字(含代码与格式)
提示:实际使用时可根据需要调整代码注释或示例的详细程度。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。