Remove Duplicates from Sorted Array II 题解
题目来源：https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/
Description
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
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.
Solution
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.empty())
return 0;
int size = nums.size();
int id = 1;
int dupTimes = 0;
for (int i = 1; i < size; i++) {
if (nums[i] != nums[i - 1]) {
nums[id++] = nums[i];
dupTimes = 0;
} else {
++dupTimes;
if (dupTimes < 2)
nums[id++] = nums[i];
}
}
return id;
}
};解题描述
这道题题意是第一版的进阶：对已经排序的数组进行原地去重（即不使用额外空间），但是允许重复元素最多出现2次。这里的解法跟第一版基本相同，只是多用了一个计数器dupTimes，每次有重复元素就计数，没有重复元素就归零，重复不超过2次就与不重复视为一样。