Leecode刷题【1数组专题4】80. 删除排序数组中的重复项II （以及通用解法）_宫水三叶 leecode

题目：

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

思路 双指针法：

写说一下自己最开始的思路，可能是以前嵌入式硬件编程总用标志位flag习惯了，思来想去，没想到别的，居然还是用了设置一个计数cnt和flag标志位。非常不出意外的，最后运行成功了18个例子之后，失败了，

（错误代码）

int removeDuplicates(int* nums, int numsSize){
    int fast = 0,slow = 0;
    int cnt = 0,flag = 0;
    for(int i = 0;i < numsSize;i++)
    {
        if(nums[fast] == nums[slow])
        {
            cnt++;
            flag = 1;
            if(cnt >= 3)
            {
                flag = 0;
                cnt = 0;
            }
        }

        if(nums[fast] != nums[slow] || (flag == 1 && nums[fast] == nums[slow]) )
        {
            int temp = nums[fast];
            nums[fast] = nums[slow];
            nums[slow++] = temp;
        }
        fast++;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

已经不知道问题出在哪儿，有点怪异，这个3，按理说不应该没有啊？？？

正解：

具体地，我们定义两个指针 slow 和 fast 分别为慢指针和快指针，其中慢指针表示处理出的数组的长度，快指针表示已经检查过的数组的长度，即 nums[fast] 表示待检查的第一个元素，nums[slow−1] 为上一个应该被保留的元素所移动到的指定位置。

因为本题要求相同元素最多出现两次而非一次，所以我们需要检查上上个应该被保留的元素 nums[slow−2]是否和当前待检查元素 nums[fast]相同。当且仅当 nums[slow−2]=nums[fast]时，当前待检查元素 nums[fast]不应该被保留（因为此时必然有 nums[slow−2]=nums[slow−1]=nums[fast]）。最后，slow 即为处理好的数组的长度。

特别地，数组的前两个数必然可以被保留，因此对于长度不超过 222 的数组，我们无需进行任何处理，对于长度超过 222 的数组，我们直接将双指针的初始值设为 222 即可。

int removeDuplicates(int* nums, int numsSize){
    int index = 0;
    for(int i = 0;i < numsSize;i++)
    {
        if(nums[i] != nums[index])
            nums[++index] = nums[i];
    }
    return index+1;
}
1
2
3
4
5
6
7
8
9

通用解法：

已经做了好几道这个删除题了，为了让解法更具有一般性，我们将原问题的「保留 2 位」修改为「保留 k 位」。
对于此类问题，我们应该进行如下考虑：

• 由于是保留 k 个相同数字，对于前 k 个数字，我们可以直接保留
• 对于后面的任意数字，能够保留的前提是：与当前写入的位置前面的第 k 个元素进行比较，不相同则保留
  比如，我们令 k=2，假设有如下样例
  [1,1,1,1,1,1,2,2,2,2,2,2,3]

1. 首先我们先让前 2 位直接保留，得到 1,1
2. 对后面的每一位进行继续遍历，能够保留的前提是与当前位置的前面 k 个元素不同（答案中的第一个 1），因此我们会跳过剩余的 1，将第一个 2 追加，得到 1,1,2
3. 继续这个过程，这时候是和答案中的第 2 个 1 进行对比，因此可以得到 1,1,2,2
4. 这时候和答案中的第 1 个 2 比较，只有与其不同的元素能追加到答案，因此剩余的 2 被跳过，3 被追加到答案：1,1,2,2,3

这是一种针对「数据有序，相同元素保留 k 位」问题更加本质的解法，该解法是从性质出发提炼的，利用了「数组有序 & 保留逻辑」两大主要性质。

class Solution {
    public int removeDuplicates(int[] nums) {   
        return process(nums, 2);
    }
    int process(int[] nums, int k) {
        int u = 0; 
        for (int x : nums) {
            if (u < k || nums[u - k] != x) nums[u++] = x;
        }
        return u;
    }
}

作者：宫水三叶
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/solutions/702970/gong-shui-san-xie-guan-yu-shan-chu-you-x-glnq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17