Medium

题目描述

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

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

说明:

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

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

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

// nums 是以"引用"方式传递的。也就是说，不对实参进行拷贝
int len = removeDuplicates(nums);

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

示例 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 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 已按升序排列

解题思路

这道题是经典的双指针问题，需要在原地修改数组，保证每个元素最多出现两次。

思路分析

方法一：双指针法（推荐） 使用快慢指针的思想：

  • slow 指针指向下一个要填入的位置
  • fast 指针用于遍历数组
  • 由于每个元素最多保留两次，当 slow >= 2 时，只有当前元素与 nums[slow-2] 不同时才能保留

核心观察：如果当前元素 nums[fast] 与 nums[slow-2] 相同，说明前面已经有两个相同元素了，当前元素应该跳过。

方法二：计数法 维护一个计数器，记录当前元素的出现次数。但这种方法代码相对复杂。

算法流程：

  1. 初始化慢指针 slow = 0
  2. 遍历数组，对于每个元素：
    • 如果 slow < 2 或 nums[fast] != nums[slow-2]，则保留当前元素
    • 将 nums[fast] 赋值给 nums[slow]，并递增 slow
  3. 返回 slow 作为新数组长度

时间复杂度 O(n)，空间复杂度 O(1)，是最优解法。

代码实现

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.size(); fast++) {
            if (slow < 2 || nums[fast] != nums[slow - 2]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
};

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 0
        for fast in range(len(nums)):
            if slow < 2 or nums[fast] != nums[slow - 2]:
                nums[slow] = nums[fast]
                slow += 1
        return slow

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.Length; fast++) {
            if (slow < 2 || nums[fast] != nums[slow - 2]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

var removeDuplicates = function(nums) {
    let slow = 0;
    for (let fast = 0; fast < nums.length; fast++) {
        if (slow < 2 || nums[fast] !== nums[slow - 2]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需遍历数组一次，n 为数组长度
空间复杂度O(1)只使用了常数个额外变量

相关题目