先来回顾一下上期的问题及答案:
「移除元素」(Remove Element)。
题目描述:
给你一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为了符合题目要求,你需要使用「原地」修改输入数组,并在函数内部直接修改输入数组,而不是创建新的数组。
示例:
输入:nums = [3,2,2,3], val = 3输出:2, nums = [2,2]解释:函数应该返回新的长度 2,并且原数组 nums 的前两个元素被修改为 2。不需要考虑数组中超出新长度后面的元素。
提示:
由于题目要求原地修改输入数组,因此可以使用双指针的方法。
使用两个指针,一个指针 slow 指向当前需要被覆盖的位置,一个指针 fast 用于遍历数组。
初始化时,两个指针都指向数组的第一个元素。
遍历数组,当 fast 指针指向的元素不等于目标值 val 时,将其复制到 slow 指针指向的位置,并将 slow 指针后移一位。
继续遍历,直到 fast 指针遍历完整个数组。
返回 slow 的值,即为删除目标元素后的新数组长度。
以下是对应的 TypeScript 解答:
function?removeElement(nums:?number[],?val:?number):?number?{
let?slow?=?0;
for?(let?fast?=?0;?fast?<?nums.length;?fast++)?{
if?(nums[fast]?!==?val)?{
nums[slow]?=?nums[fast];
slow++;
}
}
return?slow;
}
解题思路:
使用双指针的方法,一个指针 slow 指向当前需要被覆盖的位置,一个指针 fast 用于遍历数组。
初始化时,两个指针都指向数组的第一个元素。
遍历数组,当 fast 指针指向的元素不等于目标值 val 时,将其复制到 slow 指针指向的位置,并将 slow 指针后移一位。
继续遍历,直到 fast 指针遍历完整个数组。
返回 slow 的值,即为删除目标元素后的新数组长度。
时间复杂度分析:
遍历数组的时间复杂度是
O(N),其中 N 是数组的长度。
空间复杂度分析:
使用了常数个额外变量,空间复杂度为 O(1)。
2023年7月4日
「移除元素」(Remove Element)。
题目描述:
给你一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为了符合题目要求,你需要使用「原地」修改输入数组,并在函数内部直接修改输入数组,而不是创建新的数组。
示例:
输入:nums = [3,2,2,3], val = 3输出:2, nums = [2,2]解释:函数应该返回新的长度 2,并且原数组 nums 的前两个元素被修改为 2。不需要考虑数组中超出新长度后面的元素。
提示:
由于题目要求原地修改输入数组,因此可以使用双指针的方法。
使用两个指针,一个指针 slow 指向当前需要被覆盖的位置,一个指针 fast 用于遍历数组。
初始化时,两个指针都指向数组的第一个元素。
遍历数组,当 fast 指针指向的元素不等于目标值 val 时,将其复制到 slow 指针指向的位置,并将 slow 指针后移一位。
继续遍历,直到 fast 指针遍历完整个数组。
返回 slow 的值,即为删除目标元素后的新数组长度。
领取专属 10元无门槛券
私享最新 技术干货