1. 题目描述

problem link

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.

2. 解题

这道题是Remove Duplicates From Sorted Array的升级版。首先有了前面那个题的基础，这道题的大方向也是同样的思路，只不过在一些细节的地方需要做些改动。

之前的题因为最终只需要每个元素出现一次就行了，所以j在往后找的时候找到一个不等于arr[i]的元素，就把这个元素赋值到i的后面就行了。但这道题的要求是每个元素至多出现2次，所以我的思路是用一个变量sign记录i指向的元素是否出现了两次及以上，等到j找到一个不等于arr[i]的元素的时候，先判断sign是0还是大于0，是0说明i指向的元素只出现了一次，所以直接把j指向的元素赋值到i的后面就行了，但如果sign大于0，说明i指向的元素出现了重复，所以要先把i后面的元素填充为i所指向的元素，再把再后面一个的元素赋值成j指向的元素，就行了。

下面是图像解释:

初始还是i为0，j为1，发现这时候arr[i]和arr[j]相等，所以让sign等于1，表示现在i指向的元素出现了重复，然后让j一直往后找，直到找到一个不等于arr[i]的元素。

这时候找到了，然后判断sign的值，如果sign的值等于1，则需要先把i后面的元素也赋值成i指向的元素，但这个例子里本身就是1，所以看起来数组没有变化。然后就是把j指向的元素赋值到i的后两个元素的位置，并调整i和j的位置。

这就是算法的全过程。还有一个特殊情况需要考虑，如果数组的最后几个元素都是重复的，那么j会一直往后找直到走出数组的区域，这时候循环就直接跳出了，所以需要在循环外面再额外处理一下这种情况。

3. 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) {
        return numsSize;
    }

    int i = 0, j = 1;

    // 设置一个sign变量记录找到的元素是否是重复的，重复的为1，不重复为0
    int sign = 0;

    while (i < numsSize && j < numsSize) {
        if (nums[i] != nums[j]) {
            if (sign == 1) {  // 如果i指向的元素是重复的，则把i后面的元素也填充为i的元素
                i++;
                nums[i] = nums[i - 1];
            }
            i++;
            nums[i] = nums[j];
            j++;
            sign = 0;
        }
        else {
            sign = 1;
            j++;
        }
    }
    if (sign == 1) {  // 如果此时sign等于1说明数组最后几个元素是重复的，要在这里单独处理一下
        i++;
        nums[i] = nums[i - 1];
    }

    return i + 1;
}

int main() {
    int arr[] = { 1, 1, 2 };
    int res = removeDuplicates(arr, sizeof(arr) / sizeof(arr[0]));
    printf("res = %d\n", res);
    printf("\n");

    system("pause");
    return 0;
}

4. 进阶解法

又到了评论区大佬使用降维打击的时候了。先上代码，根据代码解释思路。

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) {
        return numsSize;
    }

    int i = 0;
    for (int n = 0; n < numsSize; n++) {
        if (i < 2 || nums[n] > nums[i - 2]) {
            nums[i++] = nums[n];
        }
    }

    return i;
}

变量i标志现在要填充的位置，变量n遍历数组。根据循环里的思路，首先在i等于0和1的时候if立刻成立，执行下面的语句，就是相当于跳过前两个数据不处理。然后i加到了2，n也是2。现在把视野放到i的前两个元素上，可以知道要么这两个数是相等的要么是递增的，那么我让nums[n]和nums[i-2]比较大小，也就是和i往前2个位置的元素比较大小，假如前两个数是递增的，例如下面这个情况:

那么不管nums[n]是等于2或者是大于2，最终if都成立，所以这个位置会赋上这个等于或大于2的数。

但假如前两个数是相等的，例如下面：

那么只有arr[n]大于2才能通过if从而赋值，而等于2就不赋值。可以想到，这样就保证了最终的结果里每个元素至多出现了两次！！！

这个方法不仅写法简单，更厉害的地方是可以非常轻易的扩展到至多出现K个重复元素的问题上：

int removeDuplicatesK(int* nums, int numsSize, int k) {
    if (numsSize == 0) {
        return numsSize;
    }

    int i = 0;
    for (int n = 0; n < numsSize; n++) {
        if (i < k || nums[n] > nums[i - k]) {
            nums[i++] = nums[n];
        }
    }

    return i;
}