3、删除排序数组中的重复项

题目

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

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

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。
示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。
说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

代码示例

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
    
    }
};

leetcode《删除排序数组中的重复项》原题链接

思路

当时拿到题，一看是删除数组的重复元素，第一反应是使用set，
因为set是一个内部有序且不含重复元素的容器。但题目要求是不使用额外的数组空间，只有O(1)的额外空间，所以就没法使用set了。
既然不能使用set那就老老实实删吧，因为一开始没想那么多，只想着碰到重复的就直接删掉嘛，最后容器的size就是输出的长度嘛，思路就是一位一位进行比较，如果后一位跟前一位重复，就删掉后一位

代码如下

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0) return 0;
        int temp = nums[0];//temo记录当前最新的不重复值
        int length = nums.size();
        for(int i=1;i<length;i++)
        {
            if(nums[i] == temp) //如果重复
            {
                nums.erase(nums.begin()+i);//删掉后一位
                length--;	//更新数组长度
                i--;	//因为删掉了后一位，那么意味着i就不能更新，因此这里i-1
            }
            else temp = nums[i];//不重复的话就更新temp
        }
        return nums.size();
    }
};

测试通过，当我提交上去之后耗时达到了220ms，只超过了大约17%的人，
显然这种方法不好，因为当重复时有删除的操作，显然是要增加很多时间的。
而题目明确说了，只需要让数组前面几个元素是不重复的就行，无需关注后面的元素，所以删除元素这个操作显然就是多余的，那么就只需要更改前面的元素就行。

思路

这个时候就可以设置两个迭代器或者下标 i 和 j ，
i 一直遍历，
遇到重复值就接着遍历，
遇到不重复的值就改变nums[++j] = nums[i]，也就是说把前面的元素更改为不重复的值，称为双指针法

代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //双指针法，只改变数组前面几位元素，后面的元素不管
        if(nums.size()<2) return nums.size();
        int j = 0;
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i] != nums[j]) nums[++j]=nums[i];
        }
        return ++j;
    }
};

这个思路提交后耗时36ms，但是依然只战胜了45%的人，那就证明方法还是不够好，
查看了题解区才发现，还有一个优化没有做到，就是双指针法这里还可以再优化一下
也就是当数组中的两个相邻元素不重复时，上述代码会做一个复制操作，将 nums[++j] 变为 nums[i] ，那么就存在一个问题，如图所示

如果 i 和 j 本就相邻，此时判断为nums[i] != nums[j]，
按照之前的代码，会进行一个更新 j 和数组的操作，也就是将 nums[++j] 变为 nums[i] ，
但是，nums[++j] 即 nums[1] 本来就是1，而赋值又赋为1，多此一举，增添了复制 nums[i] 的操作，完全只需要将 j 更新就行了，也就是这种情况可以优化。
但是，这里有一个条件，那就是 i 和 j 是相邻的，也就是两者差为1，一旦大于1，就需要进行复制操作了。
于是代码更改如下

代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //双指针法，只改变数组前面几位元素，后面的元素不管
        if(nums.size()<2) return nums.size();
        int j = 0;
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i] != nums[j]){
                if(i-j>1) {		//优化的地方
                    nums[++j]=nums[i];
                }
                else
                {
                    j++;
                }
            }
        }
        return ++j;
    }
};

提交之后，耗时24ms，击败了90%的用户。
虽然leetcode很多时候它的这个评测系统有问题，不准，但是还是可以作为一个参考的

一点想法

在刷leetcode的时候，
大家一定要每做完一道题之后尽量去看一看评论区，
看一看大家有没有更好的思路，
自己的程序有没有值得优化的地方，
即使自己的思路很好，多掌握几种方法也是好的嘛