题目
光看题目是非常简单的,但这里有一个限制条件,就是必须在原地修改数组,并且只能使用 O1 的额外空间。
其实前面也遇到过类似的限制,比如环形链表,当时我们的解决方案是快慢指针:事实上,在限制额外空间为 O1 的时候,通常都能使用快慢指针的方式来解决问题,这道题目的目的其实也就是帮助我们建立使用快慢指针的思维。
这里我们以数组 [1, 1, 2, 3, 3 ]
为例,创建两个指针 slow
和 fast
都指向 arr[0]
:
- 每一次遍历
fast
都自增 1 - 当
slow == fast
,则slow
不变 - 当
slow ≠ fast
,则slow
自增 1,并且将 fast 位置的值赋值过来
以上述步骤完成对整个数组的遍历之后,数组就已经实现了重排,而 slow 则指向其尾端,具体可以看看下图:
思路很简单,这里直接实现代码即可:
var removeDuplicates = function (nums) {
const len = nums.length;
let slow = 0;
for (let fast = 0; fast < len; fast++) {
if (nums[fast] !== nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
};
结果如下:
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!