题目
给你一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,并返回移除后数组的新长度。
规则示例
规则:
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
0 <= nums.length <= 100
0 <= nums <= 50
0 <= val <= 100
示例1:
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。
示例 2:
输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
解题分析一:双指针
根据每日习题No.10,我们可以很自然的联想到用双指针来解决这道题
我们以 nums = [0,1,2,2,3,0,4,2], val = 2 为例
假设
蓝色指针为slow(较慢的索引)
红色指针为fast(较快的索引)
我们从图中可以得到一些有效信息
1.每次比较 fast 和 目标值 是否相等,fast会不停往后移动
2.如果不相等,我们让slow位置内容等于fast位置内容,并且slow后移一位
**3.如果相等,不用改变slow,fast后移一位继续比较
**
4.fast超过原数组长度后则处理结束,当前slow位置则为最终数组长度
解题一:双指针
解法分析二:双指针优化(左右开工)
由于题目不要求最终结果数组的顺序,只需要去掉其中和目标值相同的内容,那么我们完全可以从数组的首尾同时开始比较,当首尾指针错位时便停止寻找
我们以 nums = [0,1,2,2,3,0,4,2], val = 2 为例
假设
蓝色指针为slow(较慢的索引)
红色指针为fast(较快的索引)
我们从图中可以得到一些有效信息
1.每次比较蓝色指针指向值和目标是否相等
2.如果不相等,则蓝色指针右移
3.如果相等,则比较红色指针指向值和目标是否相等
4.如果不相等,则将红色指针指向值赋值给蓝色指向位置,并且蓝色右移,红色左移
5.如果相等,则红色指针左移,直到找到不相等值放入蓝色位置
6.结束条件为蓝色指针位置超过红色指针位置
解法二:双指针优化(左右开工)
总结
这道题相当于是对每日习题No.10的一个巩固。同样是利用双指针来处理数组中的比较相关逻辑。并且我们还对双指针进行了一个优化,之后如果再笔试中遇到类似题目,应该可以游刃有余了。
END