leetcode 刷题记:27. 移除元素

这道题和前面的 26 题一样,要原地修改。同样我还是用快慢指针做。

问题描述

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

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

1
2
3
4
// @algorithm @lc id=27 lang=javascript 
// @title remove-element
// @test([3,2,2,3],3)=2
// @test([0,1,2,2,3,0,4,2],2)=5

解题思路

循环一遍数组,只要元素不等于val,就把快指针的元素覆盖慢指针的元素上。

方法一

这里使用到了快慢指针

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
const removeElement = function(nums, val) {
let i = 0; let j = 0;
const len = nums.length;
while (j <= len - 1) {
if (nums[j] !== val) nums[i++] = nums[j];
j++;
}
return i;
};

方法二

除了快慢指针,还可以用数组长度做文章。原因是题目不要求数组元素的位置固定,只要求删除掉指定元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
const removeElement = function(nums, val) {
let i = 0;
let len = nums.length;
while (i < len) {
if (nums[i] === val) {
nums[i] = nums[len - 1];
len--;
} else {
i++;
}
}
return len;
};