饭后小憩
官方地址：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/submissions/
问题描述
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
基本事实
比较容易想到的就是 相邻的元素进行比较，然后删除相同的相邻元素即可，重复这个过程直到数组末尾
另一种不容易想到的就是 把不重复的元素重新覆盖到元素数组中（不能使用额外数组，满足不使用额外的数组空间）
算法实现
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int size = nums.size();
if (size == 0) {
return 0;
}
if (size == 1) {
return 1;
}
int dup = nums[0];
for (int i = 1; i < size; i ++) {
if (dup == nums[i]) {
nums.erase(nums.begin() + i, nums.begin() + i + 1);
i --;
size --;
} else {
dup = nums[i];
}
}
return size;
}
};
可以看到虽然通过了这个测试，但是耗时太多了
算法实现-性能优化
上面的性能问题除出在移除重复元素的代码nums.erase(nums.begin() + i, nums.begin() + i + 1)上，下面换一种思路，就是不直接删除这个元素，而是把不重复的元素重新覆盖到nums数组中(从前往后覆盖)，以此来提升执行效率(不重复元素个数 <= 数组长度)
注意：和数组末尾元素交换后，就应该跳过数组末尾元素的遍历了
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int size = nums.size();
if (size == 0) {
return 0;
}
if (size == 1) {
return 1;
}
int count = 0;
for (int i = 1; i < size; i ++) {
if (nums[count] != nums[i]) {
count ++;
nums[count] = nums[i];
}
}
nums.resize(count + 1);
return count + 1;
}
};
可以看到执行速度得到了近10倍的提升，这个优化还是非常划算的。
一些注意的点
覆盖解法时，需要单独的计数器count来对不重复的元素进行计数