LeetCode【0027】移除元素

1 中文题目

给定一个数组 nums 和一个值 val，需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。假设 nums 中不等于 val 的元素数量为 k，要通过此题，需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

判断标准

评测机将使用以下代码测试提交的代码：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，代码将会通过。

示例：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

• $0\le nums.length\le 100$
• $0\le nums[i]\le 50$
• $0\le val\le 100$

---

2 求解方法：快慢双指针

2.1 方法思路

方法核心

使用快慢双指针（left和right）遍历数组，left指向新数组待插入位置，right遍历原数组。原地修改数组，不使用额外空间

实现步骤

• 初始化：
  • 处理空数组特殊情况
  • left指针指向0位置
• 遍历过程：
  • right指针遍历整个数组
  • 遇到不等于val的元素时，移动到left位置
  • left指针向右移动
• 结束条件：
  • right遍历完整个数组
  • 返回left的值（新数组的长度）

方法示例

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

过程演示：
初始状态：
[3,2,2,3]
l
r

1. right=0，nums[0]=3：
[3,2,2,3]
l r

2. right=1，nums[1]=2：
[2,2,2,3]
 l   r

3. right=2，nums[2]=2：
[2,2,2,3]
  l   r

4. right=3，nums[3]=3：
[2,2,2,3]
  l     r

最终结果：
返回值：2
数组前2个元素：[2,2]

2.2 Python代码

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # 如果数组为空，直接返回0
        if not nums:
            return 0
        
        # 双指针：left指向新数组待插入位置，right指向当前处理的元素
        left = 0
        
        # 遍历数组
        for right in range(len(nums)):
            # 如果当前元素不等于要删除的值
            if nums[right] != val:
                # 将该元素移动到left指向的位置
                nums[left] = nums[right]
                # left指针右移
                left += 1
        
        # 返回新数组的长度
        return left

2.3 复杂度分析

• 时间复杂度：O(n)， n是数组长度
  • 只需要遍历一次数组
  • 每个元素最多被访问一次
• 空间复杂度：O(1)
  • 只使用了两个指针变量
  • 原地修改数组，不使用额外空间

---

3 题目总结

题目难度：简单
数据结构：数组
应用算法：双指针

原文地址：https://blog.csdn.net/qq_32882309/article/details/143736947

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！