SlovinG
Search K

Appearance

80.删除有序数据中的重复项Ⅱ ​

难度：中等

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

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

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

提示：

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按升序排列

解题思路 ​

由于原数组按照升序排列，所以可以跟 27 题一个思路，采用快慢指针法。

在 26 题中，在不保留任何重复元素的情况下，我们将快指针和慢指针指向的元素进行逐个比对，每当二者的值不相同时，慢指针前进一位，并将快指针指向元素值赋给慢指针指向的位置。

但是在这个题中，我们可以保留 2 位相同的元素，那么我的做法是在 26 题的基础上加上变量 count 来对当前元素进行计数。遇到新元素，则重置计数。当遇到旧元素，但出现次数不超过 2 次时，则增加计数。

注意一开始就要检查数组长度，如果 nums.length <= 2，直接返回 nums.length。这样处理简单情况，避免进入后续循环。

这种采用 计数器 的方法直观且易于理解，特别是对于习惯了使用快慢指针技巧的开发者来说。

我的代码 ​

java
public int removeDuplicates(int[] nums) {
    int ln = nums.length;
    if (ln <= 2) {
        return ln;
    }

    int slowIndex = 0; // 慢指针指向下一个可能存放元素的位置
    int fastIndex = 1; // 快指针指向当前需要判断是否重复的元素的位置
    int count = 1;  // 当前元素的计数，初始为1，因为slowIndex从1开始

    while (fastIndex < ln) {
        if (nums[fastIndex] != nums[slowIndex]) {// 遇到新元素，重置计数
            slowIndex++;
            nums[slowIndex] = nums[fastIndex];
            count = 1;
        } else if (nums[fastIndex] == nums[slowIndex] && count < 2) {// 当遇到旧元素，但出现次数不超过2次时，增加计数
            slowIndex++;
            nums[slowIndex] = nums[fastIndex];
            count++;
        }
        fastIndex++;
    }
    return slowIndex + 1;
}

时间复杂度：O(n)

空间复杂度：O(1)

最后返回的时候，慢指针要+1，这样才是新数组真正的长度。

通用解法 ​

为了让解法更具有一般性，我们将原问题的「最多保留 1 位」修改为「最多保留 k 位」。

对于此类问题，我们应该进行如下考虑：

  • 由于是保留 k 个相同数字，对于前 k 个数字，我们可以直接保留。
  • 对于后面的任意数字，能够保留的条件是：若该数字与当前欲写入位置前面的倒数第 k 个元素值不相同则保留。因为这说明了该数字的重复次数并没有超过 k 次。

例如，假设我们令 k = 2，有样例：[3, 3, 3, 3, 4, 4, 4, 5, 5, 5]，那么代码思路为：

  1. 设定指针 slowIndex，指向待插入位置，slowIndex 初始值为 0，目标数组当前为 []

  2. 首先我们先让前 k 位直接保留。slowIndex 变为 2，目标数组为 [3, 3]

  3. 继续往后遍历，能够保留的前提是与 slowIndex 的前面倒数第 k 位元素不同，因此我们会跳过剩余的 3，将第一个 4 追加进去。slowIndex 变为 3，目标数组为 [3, 3, 4]

  4. 继续上述过程，追加第二个 4，slowIndex 变为 4，目标数组为 [3, 3, 4, 4]

  5. 当整个数组被扫描完，最终我们得到了目标数组 [3, 3, 4, 4, 5, 5] 和答案 slowIndex 为 6。

代码展示 ​

java
public int removeDuplicates(int[] nums) {
    return process(nums, 2);
}

int process(int[] nums, int k) {
    int ln = nums.length;
    int slowIndex = 0;
    int fastIndex = 0;
    while (fastIndex < ln) {
        if (slowIndex < k || nums[slowIndex - k] != nums[fastIndex]) {
            nums[slowIndex] = nums[fastIndex];
            slowIndex++;
        }
        fastIndex++;
    }
    return slowIndex;
}

时间复杂度：O(n)

空间复杂度：O(1)

总结 ​

当问题的条件是 数组有序 且要求 部分元素保留 的时候，可以考虑使用双指针法。

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