80. 删除排序数组中的重复项 II_80. 删除排序数组中的重复项 ii python

一、题目描述

略

二、思路

• 两个游标i、j，一个辅助变量id。
• j用来记录元素要复制到的位置：也就是0、1、2、3……
• i用来记录哪个元素要进行复制操作，id辅助这一过程。
• j很好说，步长为1，直接for循环j++就可以了。
• 关键是i，关键是哪个元素将要被复制：

以nums = [1,1,1,2,2,3]为例，被复制的元素是第一个1，第二个1，第一个2，第二个2，第一个3。也就是重复次数为0、1的元素。那么可以给每个元素设置身份标志id，代表着它们的特征：重复次数。

• 可以通过这段代码明确每个元素的id是多少：

id=0;
if(nums[i] == nums[i-1])
    id++;
else
    id=0;

• 当然这段代码脱离不了循环语境，这个循环可以和找i自然地放在一起：

do {
    i++;
    if(nums[i] == nums[i-1])
        id++;
    else
        id=0;
}while(id > 1);
//困于循环的i不是我们想要的i，跳出循环的i就是我们要的i

最后要考虑的就是数组越界之类的了。将在最终代码呈现的注释区域显示。

三、代码呈现

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if(n==0)
            return 0;//这里要加上空数组的情形，否则提交解答时会报错
        
        int i=0, j=1, id=0;//第0个元素一定是已就位的，所以让j直接等于1
        for(;i<n ; j++)
        {
            do{
                i++;
                if(i>=n)
                    break;//数组越界
                
                if(nums[i] == nums[i-1])
                    id++;
                else
                    id=0;
            }while(id > 1);
            
            if(i >= n)//数组越界
                break;
            nums[j] = nums[i];
        }
        return j;
    }
};