快慢指针
解析思路
-
数组是有序的，那么重复的元素一定会相邻；
- 比较 slow 和 fast 位置的元素是否相等；
- 如果相等 fast 后移 1 位；
- 如果不相等，此时说明 slow 和 fast 之间都是重复的，fast 位置的元素是不重复的元素，slow 后移 1 位，将 fast 位置的元素复制到 slow 位置上，fast 后移一位继续寻找不同的值；
-
重复上述过程，直到 fast 等于数组长度；
-
返回 slow + 1 即为新数组长度；
图解
复杂度
-
时间复杂度：
O(n) -
空间复杂度：
O(1)
代码实现
function removeDuplicates(nums: number[]): number {
let slow: number = 0;
let fast: number = 0;
while (fast < nums.length) {
if (nums[fast] !== nums[slow]) {
slow++;
nums[slow] = nums[fast];
// [nums[slow], nums[fast]] = [nums[fast], nums[slow]]; // 替换和交换均可以
}
fast++;
}
return slow + 1;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 27. 移除元素
上一篇
评论
