JS leetcode 移除元素 题解分析

2021-02-16 04:18

阅读:554

壹 ? 引

又到了每日一道算法题的环节,今天做的题同样非常简单,题目来源leetcode27. 移除元素,题目描述如下:

给你一个数组 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

注意这五个元素可为任意顺序。

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

同样,我先说说我的解题思路,再分享更优的做法。

贰 ? 解题思路

即便是未了解过算法的同学我想应该都能轻易做出,题目要求很明了,给定一个数组与一个目标值,删除数组中与目标值相同的元素,最终返回操作完的数组长度。

这里我首先想到的肯定是直接使用splice删除符合条件的元素,直接贴代码:

/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/

var removeElement = function (nums, val) {
var i = 0,
len = nums.length;
for (; i // 如果当前项与目标值相同,则删除这一样
if (nums[i] === val) {
nums.splice(i, 1);
i--;
};
};
return nums.length;
};

思路很简单,这里我们还是简单复习一下splice方法,splice() 方法向/从数组中添加/删除项目,然后返回被删除的项目。它接受三个参数:

arrayObject.splice(index,howmany,item1,.....,itemX)

其中index表示你要操作的起点,代表数组索引;howmany表示操作的个数,比如我要删除2个,还是3个。而item1,.....,itemX表示删除之后你希望加入的新元素。

需要注意的是splice方法会直接改变原数组,并返回被删除的元素数组。

let arr = [0,1,2,3];
let arr_ = arr.splice(0,2,4,5);
console.log(arr,arr_);// [4,5,2,3] [0,1]

这段代码表示,从arr索引0处删除2个元素,也就是0,1,删除后再加入4,5,所以修改后的arr为[4,5,2,3],返回的删除元素组成新的数组[0,1]

为什么里面有个i--呢,这是因为splice操作会修改原数组,让我们删除一项后,数组的length已经发生了变化,还按照原本i++遍历,会造成遍历跳过一项的问题,i--的目的就是为了重置i。

关于删除数组某项后要i--的思路,我保持了2年,直到今天遇到这道算法题,我才被改变,来看一个更棒的写法:

/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/

var removeElement = function(nums, val) {
if(nums.length===0){
return nums.length
};
for(let i = 0;iif(val === nums[i]){
nums.splice(i,1)
}else{
i++
};
};
return nums.length
};

为了方便理解,举个例子,比如我们要删除数组[2,1,2]中的所有2,按照我前面的写法。

第一次遍历遇到2,i此时为0,删除后数组变成[1,2],i自增变成1,很明显1没判断被跳过了,所以才需要i--,让i变成-1,于是第二次遍历i++又变成了0,这样就不会跳过1了。

有没有觉得i--i++非常多余呢,上面优化的写法就是解决了这个问题,如果进行了删除操作,我们让当前的i不自增不就好了,只有不满足是才自增比较下一位。直到这段代码,改变了我2年多以来的的编程思路...

那么到这里就结束了吗?并没有,题目描述结尾有这样话,剩下的元素可为任意顺序,你不需要考虑数组中超出新长度后面的元素。

说实话我都不明白它想表达什么,直到我看了别人针对这句话想出的解答思路才明白是怎么回事。比如数组[2,1,3,2]要删除2,你可以把数组变成[1,3,2,2]都算符合答案,意思就是我得到了数组[1,3],只是这个数组超出了长度多了两个2,题目也说了不考虑超出,那么针对这个思路再给出一个实现,实现灵感来自于leetcode用户灵魂画手:

/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/

var removeElement = function(nums, val) {
let ans = nums.length;
for (let i = 0; i // 只要当前元素与val相同,就与数组后面交换
if (nums[i] == val) {
[nums[i], nums[ans - 1]] = [nums[ans - 1], nums[i]];
// 注意这里递减有两个目的
// 1.第一是保证每次交换都会往前走一位,不然一直交换最后一位了
// 2.第二是模拟删除掉val后剩余的元素个数
ans--;
} else {
i++;
};
};
return ans;
};

这个思路注释其实已经说的很明白了,符合条件的元素我们把它往数组最后面丢,用个例子来模拟一下,比如数组[3,2,1,3],我们要求去掉3的长度。

第一次遍历,i为0,nums[0]与3比较由于符合,那么当前 i 的元素就和数组最后一位互换,此时数组变成了[3,2,1,3]

注意,由于你不知道换过来的最后一位是否符合条件,所以此时 i 并不能自增,而是让ans递减,作用注释也说了。

于是仍然是nums[0]和3比较,又符合条件,这时候就不是和最后一位互换,由于ans递减,所以是倒数第二位,于是数组变成了[1,2,3,3],注意此时ans又得递减,i不变。

继续遍历,还是nums[0]与3比较,不符合,所以i自增,于是nums[1]又与目标值比较,不符合条件,最终跳出了循环。

由于有2个符合条件的元素,所以ans本质上等于原数组长度4-2=2,最终返回了2。

老实说,不看这个答案,我确实想不到这个题目描述是这个意思....当然这个实现思路确实很巧妙,也感叹大佬的思路也是够清晰。

那么关于此题就分析到这了。

本文使用 mdnice 排版


评论


亲,登录后才可以留言!