移除元素

代码随想录

https://programmercarl.com/0027.移除元素.html

题目

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

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

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

示例 1: 给定 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。

你不需要考虑数组中超出新长度后面的元素。

笔记

暴力实现

双重for循环，先遍历数组，遇到要删的元素就再遍历后面的每一个元素，并把它们向前移一位。
时间复杂度是O(n^2)，空间复杂度是O(1)。

数组方法

C++中有一个库函数叫array.erase()，可以直接删除数组中的元素，即把该元素后面的所有元素都往前提一位，时间复杂度是O(n)。
js中没有直接删除的库函数，js实现删除数组元素有以下几种方法：

1. filter()

   array.filter(item => item !== valToRemove)

2. for循环 + array.splice

   for (let idx = arr.length - 1; idx >= 0; idx --) {
       if (arr[idx] === valToRemove) {
           arr.splice(idx, 1);
       }
   }

3. splice() + indexOf()
   这个方法只能删除数组中第一个等于valToRemove的元素。

   const idx = arr.indexOf(valToRemove);
   arr.splice(idx, 1);

在本题中，我最开始的思路是filter() + forEach()，先用filter剔除不需要的元素，再把剔除后的新数组的元素逐个复制粘贴到原数组。
时间复杂度O(n)，空间复杂度O(n)。

var removeElement = function(nums, val) {
    const valArr = nums.filter(item => item !== val);
    valArr.forEach((_, idx) => {
        nums[idx] = valArr[idx];
    });
    return valArr.length;
};

双指针法（快慢指针法）

一个快指针和一个慢指针同时从数组的索引0出发，首先快指针开始一个一个地往后走，当快指针遇到要保留的元素且快指针与慢指针不在同一处时，把快指针的值赋给慢指针处，并让慢支针往后走一位。重复操作，直到快指针走到arr.length。
时间复杂度O(n)，空间复杂度O(1)。

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