描述

在第一节题目的基础上，加入一个条件：最多允许存在两个重复元素，应该怎么做呢？

输入

[1, 1, 1, 2, 3, 3, 3, 3]

输出

5

分析

在第一题分析的基础上，最直观的思路是，引入一个变量（repeatCnt）记录重复元素的个数
1，当检查的元素i和当前位置的index的值相等时，若：
1）repeatCnt小于2时，向前移动index
2）若repeatCnt大于等于2时，保持index位置不变
2，当检查的元素i和当前位置的index的值不相等时，操作和上一节相同

综上分析，在第一节的基础上写出如下代码：

int duplicatesAtMostTwice00(int A[], int n)
    {
        if (n<=2) {
            return 2;
        }
        
        int index = 0;
        int repeat = 1;
        for (int i=1; i<n; i++) {
            if (A[i] != A[index]) {
                A[++index] = A[i];
                repeat = 1;
            }
            else {
                if(repeat < 2) {
                    ++repeat;
                    ++index;
                }
            }
        }
        
        return index+1;
    }

进一步的分析

上一种做法，优点是简单易懂，缺点时代码比较冗余，我们再做进一步的思考。

在一个有重复元素的排序数组中允许存在repeatCnt个数的重复元素，则：

1，数组的前repeatCnt个元素一定是可以存在的；

2，数组中待排查元素的起始位置（i）为repeatCnt的值,i = repeatCnt;

3，数组的后续可放置元素的位置（index）为repeatCnt，index = repeatCnt;

判断元素是否可以存在的逻辑：

当前检测的位置i的元素和位置index前repeatCnt个元素不同，则可以放置到index位置上，index前移一个位置。

伪代码标识如下：

if a[i] != a[index-repeatCnt]:
    a[index++] = a[i]

依据分析，进一步的代码如下：

int duplicatesAtMostTwice01(int A[], int n)
{
    int duplicateCnt = 2;
    if (n<=duplicateCnt) {
        return n;
    }
    
    int index = duplicateCnt;
    for (int i=duplicateCnt; i<n; i++) {
        if (A[i] != A[index-duplicateCnt]) {
            A[index++] = A[i];
        }
    }
    
    return index;
}

---

总结

在有序数组中进行原地操作时，需要：

1，确定数组的起始结尾游标；

2，确定检查元素的起始游标；

3，设计逻辑判断条件，移动游标操作数组元素的移动；

---

代码在这儿