题目

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

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

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以**「引用」**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

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

示例 2：

1
2
3
输入：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题很像，区别就是保留出现两次及以内的数字。还是借助27题的思路。使用双指针index和i，index=0，i从1开始，然后计数变量count=2。这里默认相同数目为2，因为我们两个指针不是一起开始的，是一个在前面一个在后面，初始的情况可能两个数都相等，这个时候要当作不同的数处理；如果不相等，那么按照27的思路处理即可；此时还要考虑如果两个数相等进行的处理，那么count++，标记已经出现两次了，再来就是多了；如果不同数据进行的处理，那么将count初始化即可。记得返回数组长度为下标index + 1。时间复杂度超越100%，嘿嘿，真感觉自己行了o(￣▽￣)ブ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 0, count = 2;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[index] || count <= 2) {
                if (nums[i] == nums[index]){
                    count++;
                } else {
                    count = 2;
                }
                nums[++index] = nums[i];
            }
        }
        return index + 1;
    }
}

再看一遍自己的解法竟然看不懂了，orz，附上一个很好的解法：

80. 删除有序数组中的重复项 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
   public int removeDuplicates(int[] nums) {
     int k = 2; // 每个元素最多出现的次数
    if (nums.length <= k) return nums.length; // 如果数组长度小于等于 k，直接返回数组长度

    // 初始化慢指针和快指针
    int slow = k, fast = k;
    while (fast < nums.length) {
        // 如果 nums[fast] 不等于 nums[slow - k]
        // 则将 nums[fast] 复制到 nums[slow]，并将 slow 向前移动一位
        if (nums[fast] != nums[slow - k]) { //nums[slow - k] 是当前考虑的元素在新数组中的第一个可能的位置
            nums[slow] = nums[fast];
            slow++;
        }
        // 将 fast 向前移动一位，以检查下一个元素
        fast++;
    }
    // 返回新数组的长度
    return slow;
}