题目链接:leetcode-cn.com/problems/re…
方法一
解题思路
- 主要思路是遍历数组
nums
,每次取出的数组元素为num
,设置初始下标为ans
。 - 在遍历过程中,如果
num
与需要移除的值不同,则进行拷贝覆盖nums[ans] = num
,ans
自增 1。 - 如果相同,则跳过该数字不进行拷贝覆盖,最后
ans
即为新的数组长度。 - 这种思路适用于需要移除的元素较多时,最极端的情况是全部元素都需要移除,遍历一遍结束即可。
代码
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
let ans = 0;
for (const num of nums) {
if (num != val) {
nums[ans] = num;
ans++;
}
}
return ans;
};
复杂度分析:
- 时间复杂度:
- 空间复杂度:
方法二
解题思路
现在考虑数组包含很少的要删除的元素的情况。例如,,。之前的算法会对前四个元素做不必要的复制操作。另一个例子是 ,。似乎没有必要将 这几个元素左移一步,因为问题描述中提到元素的顺序可以更改。
因此,我们可以这样解本题:当我们遇到 nums[i] = val
时,我们可以将当前元素与最后一个元素进行交换,并释放最后一个元素。这实际上使数组的大小减少了 1。
请注意,被交换的最后一个元素可能是你想要移除的值。但是不要担心,在下一次迭代中,我们仍然会检查这个元素。
代码
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
let ans = nums.length;
for (i = 0; i < ans;) {
if (nums[i] == val) {
nums[i] = nums[ans - 1];
ans--;
} else {
i++
}
}
return ans;
};
复杂度分析:
- 时间复杂度:
- 空间复杂度:
更多题解请关注:github.com/leviding/le…
关注公众号「技术漫谈」加算法群,每天一道算法题,趣学算法很容易!:
- LeetCode 算法题解
- JavaScript 入门到进阶
- 前端项目从零到一实战
- 前端学习方法路线分享
- ……