80. Remove Duplicates from Sorted Array II
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Given 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 respectively.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,1,2,3,3],
Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.
It doesn't matter what values are set beyond the returned length.
Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
这一题是LeetCode Remove Duplicates from Sorted Array的升级版，如果数组中的重复元素允许最多保留2个，又应该怎么处理呢。
可以通过修改LeetCode Remove Duplicates from Sorted Array的代码实现，添加一个cnt来统计重复出现的次数，如果小于3次，则i（最多不超过2次重复的最末尾的下标）的下标还是不停往前移，否则i暂停，但j还是要往前移。如果遇到不等的元素，则重置cnt=1。完整代码如下：
class Solution {
public:
int removeDuplicates(vector<int>& nums)
{
if (nums.size() < 3)
return nums.size();
int i = 0, j = i + 1, cnt = 1;
while (j < nums.size()) {
if (nums[j] != nums[i]) {
cnt = 1;
nums[++i] = nums[j++];
}
else {
cnt++;
if (cnt < 3)
nums[++i] = nums[j++];
else
j++;
}
}
return i + 1;
}
};
本代码提交AC，用时13MS。
上面的代码理解起来有点绕，网上有一种解法还是很好理解的，直接比较当前元素和前一个元素是否相等，相等则cnt++，否则cnt=1，同时如果cnt<3，则把最多重复2次的元素往前移。完整代码如下：
class Solution {
public:
int removeDuplicates(vector<int>& nums)
{
if (nums.size() < 3)
return nums.size();
int cnt = 0, j = 0;
for (int i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i – 1]) {
cnt++;
if (cnt >= 3)
continue;
}
else {
cnt = 1;
}
nums[j++] = nums[i];
}
return j;
}
};
本代码提交AC，用时16MS。
二刷。双指针，i表示合法的填入位置，j一直往前走，如果和target相等，则填入i位置；否则更新target值。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if (n == 0)return 0;
int target_value = nums[0], target_id = 0;
int i = 0, j = 0;
while (j < n) {
while (j < n&&nums[j] == target_value) {
if (j < target_id + 2)nums[i++] = target_value;
++j;
}
if (j < n) {
target_id = j;
target_value = nums[j];
}
}
return i;
}
};
本代码提交AC，用时16MS。
