080 - Remove Duplicates from Sorted Array II

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

Hide Tags

Array Two Pointers

与 1 不同的是，如果有重复的，可以保留两个重复的值。

在1 的基础上改的，加入了一点处理：

如果while结束之后，jj的位置比ii的位置“远”，则说明有重复的值

那么就在ii的位置复制一份，再一起向前。

“远”多少呢？就是超过ii跟jj之间的已有的距离，所以加一个变量保存两者间的offset即可。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int ii = 0;
        if(nums.size())
        {
            int offset=0;                   //distance between ii and jj
            for(int jj=0; jj<nums.size(); )
            {
                nums[ii++] = nums[jj++];
                while((nums[ii-1] == nums[jj])&&(jj<nums.size()))
                    jj++;
               
                if(jj>(ii+offset))          //if jj covers more than 1 duplicate value
                {
                    nums[ii] = nums[ii-1];  //duplicate the second one
                    ii++;                   //move to next for new value
                    offset = jj-ii;         //update distance
                }
             }
        }
        return ii;
    }
};

16 ms