描述
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]
解法一
要解该题，只需要在上一题（leetcode解题报告（1）：Remove Duplicates from Sorted Array）的基础上，加一个计算重复次数的变量count，再做相应的改动即可。
代码如下：
class Solution{
public:
int removeDulicatesII(int A[],int n){
if(n <= 2) //if n <= 2,then the result is n
return n;
int index = 0; //index of new array
int count = 1; //count the duplicated elements
for(int i = 0; i != n; ++i){
if(A[index] != A[i]){ //not equal,so add this element into new array
A[++index] = A[i];
count = 1; //and reset count
//this is because that A[index] != A[i] means no constantly duplicated elements
}
else if(A[index] == A[i] && count < 2){ //if equal and count < 2
A[++index] = A[i]; //add it
++count; //increment the value of count
}
//if A[index] == A[i] and count >= 2,then skip it
}
return index + 1;
}
}
该算法的时间复杂度为O(n)，空间复杂度为O(1)。
代码略长，但是有较好的扩展性。如若将count < 2改为count < 3，结果依然正确。
解法二
如果去掉count，那么每次都要判断当前值、前一值以及下一值的值是否都相等，若相等，说明有连续3个相等的值，那么就不做处理；否则，将该值加入数组。
这引出了一个新的问题：对于第一个元素（下标为0），前一元素就会使下标为负数；对于最后一个元素（下标为n - 1），下一元素的下标会溢出。解决办法是去掉这个边界情况。
代码如下：
class Solution{
public:
int removeDuplicatesII(int A[],int n){
int index = 0;
for(int i = 0; i != n; ++i){
if(i > 0 && i < n - 1 && A[i - 1] == A[i] &&A[i + 1] == A[i])
continue;
A[index++] = A[i];
}
return index;
}
}
该算法的时间复杂度为O(n)，空间复杂度为O(1)。
由于去掉了变量count，因此该算法只适用于该题。
解法三
换种思路：将index的值设置为2，遍历从i = 2开始，每次比较A[index - 2]和A[i]是否相等，若不相等，则将该值加入新的数组，并将index加1。
代码如下：
class Solution{
public:
int removeDuplicatesII(int A[],int n){
if(n <= 2)return n;
int index = 2;
for(int i = 2; i != n; ++i){
if(A[index - 2] != A[i])
A[index++] = A[i];
//or:
//A[index] = A[i];
//index += 1;
}
return index;
}
}
注意返回的值。此处返回的是为index，而解法一返回的是index + 1。
该算法的时间复杂度为O(n)，空间复杂度为O(1)。