leetcode 刷题记:26. 删除有序数组中的重复项

这道题如果在实际工作中其实不容易遇到,因为想把一个数组去重,一个Set就足以。然而这道题有猫腻:原地修改

问题描述

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 $O(1)$ 额外空间的条件下完成。

1
2
3
4
// @algorithm @lc id=26 lang=javascript 
// @title remove-duplicates-from-sorted-array
// @test([1,1,2])=2
// @test([0,0,1,1,1,2,2,3,3,4])=5

解题思路

原本我就是使用Set来做这道题的,最后发现一直给我报错。问题就出在原地上。

1
2
3
function unique(array) {
return Array.from(new Set(array));
}

这里要把数组原地替换,把第一次出现的元素移到重复的元素位置上,实现原地修改。

因为整个数组是有顺序的,就可以用比大小的方式来判断相邻两个元素是否是相同。这里使用快慢指针的方式解决这个问题,i是插入操作指针,j是遍历指针。只要判断j指针的元素大于或者不等于i,就更新i+1位置的元素为j指针的元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {number[]} nums
* @return {number}
*/
const removeDuplicates = function(nums) {
if (nums.length === 0) return 0;
let i = 0; let j = 1;
while (j <= nums.length - 1) {
if (nums[i] === nums[j]) j++;
if (nums[i] < nums[j]) {
nums[i + 1] = nums[j];
i++;
}
}
return i + 1;
};

题外话

上面提到的Set去重数组,如果数组元素是个Object,记得深度拷贝。否则会出现去重后的数组会影响原来的数组。

我一般的深度拷贝是用下面这种,主要是我也没写代码实现过这东西。

1
JSON.parse(JSON.stringify(array))