家好，很高兴又见面了，我是姜茶的编程笔记，我们一起学习前端相关领域技术，共同进步，也欢迎大家关注、点赞、收藏、转发，您的支持是我不断创作的动力

铁子们！从 2024/07/26 开始，我们进入算法专题篇的学习啦 。学习计划如下：

1?? 每日一题;

2?? 学习顺序是由易到难；

3?? 题目按照数据结构进行分类;

4?? 每个类型的题目预计安排 100 道题（简单/中等/困难各 33 道）;

题目描述

27. 移除元素

给你一个数组 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, 1, 4, 0, 3。注意这五个元素可以任意顺序返回。你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

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

分析/求解

解决这个问题的关键在于我们要在原地操作数组，不能使用额外的空间来存储新数组，同时要保证与 val 不同的元素在数组的前 k 个位置。以下是详细的解释和多种解决方法：

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

双指针法使用两个指针，一个用于遍历整个数组，另一个用于标记新数组的末尾。遍历过程中，如果遇到与 val 不同的元素，就将这个元素放到新数组的末尾。

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历该序列至多两次
• 空间复杂度：O(1)，我们只使用了常数级别的额外空间。

function removeElement(nums, val) {
    let i=0;
    for (let j=0; j < nums.length; j++) {
        if (nums[j] !==val) {
            nums[i]=nums[j];
            i++;
        }
    }
    return i;
}

方法二：双指针法（交换法）

这种方法也是使用双指针，但不同的是，当我们找到需要移除的元素时，将其与数组的最后一个元素交换，并减少数组的长度。这样做的好处是可以减少复制操作，但数组元素的顺序会被改变。

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只遍历了一次数组。
• 空间复杂度：O(1)，我们只使用了常数级别的额外空间。

function removeElement(nums, val) {
    let i=0;
    let n=nums.length;
    while (i < n) {
        if (nums[i]===val) {
            nums[i]=nums[n - 1];
            n--;
        } else {
            i++;
        }
    }
    return n;
}

总结

对于像「移除特定元素」或「相同元素最多保留 k 位元素」这样的问题，应该利用题目给定的要求分析出具体的「保留逻辑部分」，将「保留逻辑部分」应用到我们的遍历到的每一个位置即可。

附件：

最后

如果有任何问题或建议，欢迎在评论区留言交流！祝你编程愉快！

道题的难点在于要求：不要使用额外的数组空间，必须仅使用 O(1) 额外空间并 原地 修改输入数组。

这是一道很典型的双指针题型，我们可以使用快慢指针来解决。

快慢指针

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement=function(nums, val) {
    let i=0;
    for (let j=0; j < nums.length; j ++) {
        if (nums[j] !==val) {
            nums[i++]=nums[j];
        }
    }
    return i;
};

由于题目中说明，可以改变顺序，因此，我们可以用首尾指针交换元素位置来进行优化。

首尾指针