Leetcode数组篇—javascript实现移除元素

移除元素

  题目链接&＃xff1a;移除元素 难度&＃xff1a;简单
  题目描述&＃xff1a;给你一个数组 nums 和一个值 val&＃xff0c;你需要原地移除所有数值等于val的元素&＃xff0c;并返回移除后数组的新长度。不要使用额外的数组空间&＃xff0c;你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
  说明:
  为什么返回数值是整数&＃xff0c;但输出的答案是数组呢?
  请注意&＃xff0c;输入数组是以「引用」方式传递的&＃xff0c;这意味着在函数里修改输入数组对于调用者是可见的。
  你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说&＃xff0c;不对实参作任何拷贝
let len &＃61; removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i &＃61; 0; i < len; i&＃43;&＃43;) {return nums[i];
}


  例子&＃xff1a;

实现思想&＃xff1a;(1)暴力解法&＃xff1a;首先遍历数组&＃xff0c;如果发现数组中有值为val的元素&＃xff0c;则将该元素之后的所有元素向前移动一位&＃xff0c;覆盖住val值的元素&＃xff0c;移动完成后再将数组长度减一&＃xff0c;即达到删除val值元素的效果。此时我们应该继续遍历数组&＃xff0c;由于第一个val值元素被删除了&＃xff0c;它后面的元素都向前移动了一位&＃xff0c;我们需要从移动的第一个元素开始遍历&＃xff0c;所有也需要把遍历数组的下标i减一。
  例如&＃xff1a;原数组为[3&＃xff0c;2&＃xff0c;2&＃xff0c;3]&＃xff0c;val为3。遍历的第一个元素与val相等&＃xff0c;所以我们将后面3个元素都向前移动一位并将数组长度减一&＃xff0c;结果数组是[2&＃xff0c;2&＃xff0c;3]。此时i&＃61;1&＃xff0c;但我们需要从新数组的第一个元素2开始遍历&＃xff0c;而元素2的位置下标向前移动了一位&＃xff0c;因此也要将i减一。
实现代码&＃xff1a;

//暴力解法&＃xff1a;复杂度是O(n²)
var removeElement &＃61; function(nums, val) {for(let i &＃61; 0;i < nums.length;i&＃43;&＃43;){if(nums[i] &＃61;&＃61; val){for(let j &＃61; i &＃43; 1;j < nums.length;j&＃43;&＃43;){nums[j - 1] &＃61; nums[j]; //后面元素向前移动一位,覆盖值为val的元素}nums.length--; //数组长度减一,达到删除值为val的元素的效果i--; //元素向前移动一位,所以遍历下标也要减一}}return nums.length; //返回数值是整数,但输出的答案是数组
};


(2)双指针法&＃xff1a;右指针right指向当前将要处理的元素&＃xff0c;左指针left指向下一个将要赋值的位置。最开始时left&＃61;right&＃61;0&＃xff0c;然后两个指针都慢慢向右移动。

• 如果右指针指向的元素不等于val&＃xff0c;它一定是输出数组的一个元素&＃xff0c;我们就将右指针指向的元素复制到左指针位置&＃xff0c;然后将左右指针同时右移
• 如果右指针指向的元素等于val&＃xff0c;它不能在输出数组里&＃xff0c;此时左指针不动&＃xff0c;右指针右移一位。

整个过程保持不变的性质是&＃xff1a;区间[0,left) 中的元素都不等于val。当左右指针遍历完输入数组以后&＃xff0c;left的值就是输出数组的长度。
这样的算法在最坏情况下&＃xff08;输入数组中没有任何元素等于val&＃xff09;&＃xff0c;左右指针各遍历了数组一次&＃xff0c;时间复杂度为O(n)。
实现代码&＃xff1a;

//双指针法,最坏情况下左右指针各遍历了数组一次
var removeElement &＃61; function(nums, val) {let left &＃61; 0;for(let right &＃61; 0;right < nums.length;right&＃43;&＃43;){if(nums[right] !&＃61; val){nums[left] &＃61; nums[right];left&＃43;&＃43;;}}return left;
};


  以上双指针都是从头开始遍历的&＃xff0c;最坏情况下两个指针都要完全遍历一次数组&＃xff0c;另外当left&＃61;right&＃61;0时&＃xff0c;若第一个元素的值等于val&＃xff0c;则要将其他元素向前移动一位&＃xff08;保证left前的元素都不为val&＃xff09;&＃xff0c;考虑到这种情况下较为麻烦&＃xff0c;所以可以将双指针进行改进&＃xff0c;使两个指针初始时分别位于数组的首尾&＃xff0c;分别向中间移动遍历该序列。

• 如果左指针left指向的元素等于val&＃xff0c;此时将右指针right指向的元素复制到左指针left的位置&＃xff0c;然后右指针right左移一位。如果赋值过来的元素恰好也等于val&＃xff0c;可以继续把右指针right指向的元素的值赋值过来&＃xff0c;直到左指针指向的元素的值不等于val为止。
• 当左指针left和右指针right重合的时候&＃xff0c;左右指针遍历完数组中所有的元素。

  这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与前一种双指针方法不同的是&＃xff0c;这种两头指针避免了需要保留的元素的重复赋值操作。
实现代码&＃xff1a;

//双指针法改进
var removeElement &＃61; function(nums, val) {let left &＃61; 0, right &＃61; nums.length;while(left < right){if(nums[left] &＃61;&＃61; val){nums[left] &＃61; nums[right-1];right--;}else{left&＃43;&＃43;;}//if(nums[left] !&＃61; val){// left&＃43;&＃43;;//}else{// nums[left] &＃61; nums[right-1];// right--;//}}return left;
};