## 题目地址

https://leetcode.com/problems/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]);
}
``````

## 思路

``````class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int pre = 0, cur = 1, cnt = 1, n = nums.size();
while (cur < n) {
if (nums[pre] == nums[cur] && cnt == 0) ++cur;
else {
if (nums[pre] == nums[cur]) --cnt;
else cnt = 1;
nums[++pre] = nums[cur++];
}
}
return nums.empty() ? 0 : pre + 1;
}
};

``````

``````class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int i = 0;
for (int num : nums) {
if (i < 2 || num > nums[i - 2]) {
nums[i++] = num;
}
}
return i;
}
};
``````

### 思路2

”删除排序“类题目截止到现在（2020-1-15）一共有四道题：

。 那么这道题 k 就是 2， 26.remove-duplicates-from-sorted-array 的 k 就是 1。

• 初始化快慢指针 slow ， fast ，全部指向索引为 0 的元素。
• fast 每次移动一格
• 慢指针选择性移动，即只有写入数据之后才移动。是否写入数据取决于 slow - 2 对应的数字和 fast 对应的数字是否一致。
• 如果一致，我们不应该写。 否则我们就得到了三个相同的数字，不符合题意
• 如果不一致，我们需要将 fast 指针的数据写入到 slow 指针。
• 重复这个过程，直到 fast 走到头，说明我们已无数字可写。

• 快慢指针
• 读写指针
• 删除排序问题

## 代码

Python Code：

``````class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# 写指针
i = 0
K = 2
for num in nums:
if i < K or num != nums[i-K]:
nums[i] = num
i += 1
return i
``````

## 相关题目

1. 删除排序链表中的重复元素 II

1. 删除排序链表中的重复元素

评论
0 评论