Remove Duplicates from Sorted Array II

Source

• lintcode: (101) Remove Duplicates from Sorted Array II

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

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

Your function should return length = 5, and A is now [1,1,2,2,3].
Example

题解

在上题基础上加了限制条件元素最多可重复出现两次。因此可以在原题的基础上添加一变量跟踪元素重复出现的次数，小于指定值时执行赋值操作。但是需要注意的是重复出现次数occurence的初始值(从1开始，而不是0)和reset的时机。

C++

class Solution {
public:
    /**
     * @param A: a list of integers
     * @return : return an integer
     */
    int removeDuplicates(vector<int> &nums) {
        if (nums.size() < 3) {
            return nums.size();
        }

        int size = 0;
        int occurence = 1;
        for (vector<int>::size_type i = 1; i != nums.size(); ++i) {
            if (nums[size] != nums[i]) {
                nums[++size] = nums[i];
                occurence = 1;
            } else if (nums[size] == nums[i]) {
                if (occurence++ < 2) {
                    nums[++size] = nums[i];
                }
            }
        }

        return ++size;
    }
};

源码分析

1. 在数组元素小于3(即为2)时可直接返回vector数组大小。
2. 初始化occurence的值为1，而不是0. 理解起来也方便些。
3. 初始化下标值i从1开始
   • nums[size] != nums[i]时递增size并赋值，同时重置occurence的值为1
   • (nums[size] == nums[i])时，首先判断occurence的值是否小于2，小于2则先递增size，随后将nums[i]的值赋给nums[size]。这里由于小标i从1开始，免去了对i为0的特殊情况考虑。
4. 最后返回size + 1，即为++size