题目链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

题目描述:

给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

题目重点: 原地,只能是修改入参nums的引用,(备注:工程实践中这样其实一点都不好)

解法1

因为是一个已经排序的数组,所以有序很关键,想知道是否重复,直接对比前一项就好了。如果是重复的,我们直接删除就行了。

1
2
3
4
5
6
7
8
9
10
11
var removeDuplicates = function(nums) {
if (nums.length === 0) return 0;
let size = nums.length;
for (let j = 1; j < size; j++) {
if (nums[j] === nums[j-1]) {
nums.splice(j, 1);
j--; // 注意因为splice改变了数组的长度,并且导致下一个本该比较的元素前移到了当前被删除元素的位置,所以游标需要减去1
}
}
return nums.length
};

备注: 上述思路超时,这说明直接改变数组的长度不是一个很好的方法。

解法2

双指针的思路,一个快指针,一个慢指针,也是这道题的一个官方解法。其中慢指针永远指向该数组不重复的最后一个,最后i就是不重复的最后一项。

1
2
3
4
5
6
7
8
9
10
11
12
13

var removeDuplicates = function(nums) {
if (nums.length === 0) return 0;
let size = nums.length;
let i = 0;
for (let j = 1; j < size; j++) {
if (nums[j] !== nums[i]) {
i++;
nums[i] = nums[j]
}
}
return i + 1;
};

解法3

使用计数的方法,因为有重复数字,所以当前数字有可能本不该出现在当前位置,本质上让当前数字出现在本该出现的位置。

1
2
3
4
5
6
7
8
9
10
11
12
var removeDuplicates = function(nums) {
if (nums.length === 0) return 0;
let cnt = 0;
let size = nums.length;
for (let j = 1; j < size; j++) {
if (nums[j] === nums[j-1]) {
cnt++
}
nums[j-cnt] = nums[j]
}
return size - cnt;
};

总结

有序数组的特性保证了我们可以方便快速的利用前后关系判断是否有重复元素,接下来的关键就是如何将不重复的数字放在本应该出现的位置上。注意题目的「原地」的概念,这里会出现元素复制的操作。