企业官网建设流程全解析

题目

27. 移除元素 - 力扣（LeetCode）

给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。

假设nums中不等于val的元素数量为k，要通过此题，您需要执行以下操作：

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

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

示例 2：
输入：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 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

题解

解题思路

• 方法：双指针（快慢指针）

• 时间复杂度: O(n)

• 空间复杂度: O(1)

• 前提理解：题目要求原地移除，也就是说不能另外开一个新数组把要保留的元素装进去，只能在原来的数组nums上动手。"移除"的本质是把要保留的元素往前搬，覆盖掉要删除的元素，然后返回新的长度，搬完之后后面多出来的那部分元素是什么并不重要

• 过程：

  1. 定义慢指针slow，它指向新数组里下一个要填充的位置，初始为 0。同时它也可以理解为"当前已经保留的元素个数"
  2. 定义快指针fast，它负责从头到尾扫描整个原数组，初始也为 0
  3. 让快指针不断向数组的右边前进，可以使用for循环，当循环结束时，说明整个数组已经遍历完，直接返回slow，即数组长度，程序结束
  4. 每进入一个循环，都要进行以下判断：
     1. nums[fast] != val //val为要删除的目标值，说明快指针fast所指的这个元素不是目标值val，需要保留，如何保留呢，把它搬到慢指针所在的位置，即nums[slow] = nums[fast]，然后慢指针后移一位slow++
     2. 不符合上面的条件直接印证快指针fast所对应的值刚好为目标值val，这个时候快指针fast直接前进，而慢指针slow不变，这样如果有下一次循环，则快指针fast所对应的值直接赋值给慢指针fast所对应的值，刚好完成删除数组元素。
  5. 循环结束时，slow的值正好就是与val不同的元素数量，也就是题目要返回的k，同时可以说是新数组的长度。

• 补充方法：相向双指针（头尾指针）
  如果数组中等于val的元素很少，可以让左右指针从两端往中间夹：右指针指向"还没处理的那部分的末尾"，当nums[left] == val时，就用nums[right]，即右边没有问题的元素把这个位置等于val的元素覆盖掉，然后right--；否则left++。它的思想是"用尾部不需要保留的元素来填前面的坑"，能少搬一些元素，缺点是会打乱元素的相对顺序

图解

代码实现

伪代码

slow = 0 for fast = 0 to nums.size - 1 { if nums[fast] != val nums[slow] = nums[fast] slow++ } return slow

Java实现

class Solution { public int removeElement(int[] nums, int val) { int slow = 0; for (int fast = 0; fast < nums.length; fast++) { if (nums[fast] != val) { nums[slow] = nums[fast]; slow++; } } return slow; } }

C语言实现

int removeElement(int* nums, int numsSize, int val) { int slow = 0; for (int fast = 0; fast < numsSize; fast++){ if (nums[fast] != val){ nums[slow] = nums[fast]; slow++; } } return slow; }

Python实现

from typing import List class Solution: def removeElement(self, nums: List[int], val: int) -> int: slow = 0 for fast in range(len(nums)): if nums[fast] != val: nums[slow] = nums[fast] slow += 1 return slow

参考

代码随想录

力扣官方题解（题目页里的题解区，可以对照快慢指针和相向双指针两种写法）

OI Wiki（算法竞赛向的知识库，双指针、二分等专题都有）

Hello 算法（开源算法教程，同一份代码有 Java / C / Python 三个版本）