【LeetCode】80. Remove Duplicates from Sorted Array II （删除排序数组中的重复项 II）-C++实现及详细图解

问题描述：

（1）创建一个辅助函数，找出下一个不析相等元素的选表

private:
    int nextIndex(const vector<int>& nums, int index){
        for(int i = index ; i < nums.size() ; i ++)
            if(nums[i] != nums[index])
                return i;  //返回i:相等元素的个数
        return nums.size();
    }

 如图数组：

下一个不相等元素为2，所以函数返回3

（2） 设

        int i = 0; //被替换的元素的下标（重复的元素）
        int j = 0; //要替换的元素的下标（不重复的元素）

（3）第一轮while循环

while(j < nums.size())

则 int k = nextIndex(nums, j);

 int len = min( 2, k-j);

 for(int ii = 0 ; ii < len ; ii ++)
                nums[i+ii] = nums[j];

第一轮for循环：

ii++;

第二轮for循环：

 

（4）第二轮while循环 

i  = 2;

j = 3;

k = nextIndex(nums, 3) = 5'

len =min( 2, k-j) = 2;

执行for循环：

      for(int ii = 0 ; ii < len ; ii ++)
                nums[i+ii] = nums[j];

第一轮for循环：

第二轮for循环： 

（5）第三轮while循环  

i  = 4;

j =  5;

k = nextIndex(nums, 5) = 6

len =min( 2, 1) = 2;

执行for循环：

            for(int ii = 0 ; ii < len ; ii ++)
                nums[i+ii] = nums[j];

第一轮for循环：

第一轮for循环：

ii < len 不成立，循环结束

 

（6）最后，附上完整代码：

#include <iostream>
#include <vector>

using namespace std;

/// Ad-Hoc
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {

        int i = 0; //被替换的元素的下标（重复的元素）
        int j = 0; //要替换的元素的下标（不重复的元素）
        while(j < nums.size()){
            int k = nextIndex(nums, j); //找出下一个不相同元素的下标
            int len = min( 2, k-j); //允许重复的元素个数，最多不可以超过2个
            for(int ii = 0 ; ii < len ; ii ++)
                nums[i+ii] = nums[j];
            i += len; //跳到下一组元素
            j = k;//下一个不相同元素的下标
        }

        return i;
    }

private:
    int nextIndex(const vector<int>& nums, int index){
        for(int i = index ; i < nums.size() ; i ++)
            if(nums[i] != nums[index])
                return i;  //返回i:相等元素的个数
        return nums.size();
    }
};


int main() {

    vector<int> nums1 = {1, 1, 1, 2, 2, 3};
    cout << Solution().removeDuplicates(nums1) << endl;

    return 0;
}

 

参考资料：

https://github.com/liuyubobobo/Play-Leetcode