江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第27题：移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

题目描述

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

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

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

难度

简单

题目链接

https://leetcode.cn/problems/remove-element/

示例

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

解题思路

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

使用快慢指针的方法，慢指针指向当前可以放置元素的位置，快指针用于遍历数组。

关键点：

  1. 使用快慢指针处理
  2. 原地修改数组
  3. 不需要保持元素相对顺序

具体步骤：

  1. 初始化慢指针slow = 0
  2. 使用快指针fast遍历数组：
    • 如果nums[fast] != val，将元素复制到slow位置
    • slow指针前进一位
  3. 返回slow（新数组的长度）

时间复杂度：O(n)，其中n是数组的长度 空间复杂度：O(1)

方法二：双指针（首尾指针）

使用首尾指针的方法，当遇到需要移除的元素时，用数组末尾的元素替换它。

关键点：

  1. 使用首尾指针
  2. 从数组末尾获取替换元素
  3. 适用于移除元素较少的情况

具体步骤：

  1. 初始化左指针left = 0，右指针right = nums.length - 1
  2. 当left <= right时：
    • 如果nums[left] == val，用nums[right]替换，right–
    • 否则left++
  3. 返回left（新数组的长度）

代码实现

C# 实现（快慢指针）

public 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# 实现（首尾指针）

public class Solution {
    public int RemoveElement(int[] nums, int val) {
        int left = 0;
        int right = nums.Length - 1;
        
        while (left <= right) {
            if (nums[left] == val) {
                nums[left] = nums[right];
                right--;
            } else {
                left++;
            }
        }
        
        return left;
    }
}

代码详解

快慢指针版本：

  1. 指针使用：
    • slow指向可以放置元素的位置
    • fast用于遍历数组
  2. 元素处理：
    • 只复制不等于val的元素
    • 保证原地修改

首尾指针版本：

  1. 指针使用：
    • left从左向右遍历
    • right指向有效元素的末尾
  2. 元素处理：
    • 用末尾元素替换需要移除的元素
    • 减少元素移动次数

执行结果

快慢指针版本：

  • 执行用时：108 ms
  • 内存消耗：40.2 MB

首尾指针版本：

  • 执行用时：104 ms
  • 内存消耗：40.1 MB

总结与反思

  1. 这是一道基础的数组处理题目：
    • 考察指针的使用
    • 考察原地修改数组
    • 考察空间效率
  2. 两种解法比较：
    • 快慢指针：实现简单，适用性强
    • 首尾指针：移动次数少，但会改变元素顺序
  3. 优化思路：
    • 可以根据val出现频率选择算法
    • 考虑数组特征选择最优解法
    • 注意边界条件的处理

相关题目