每日一题20250209-LC80

题目信息

题目难度：medium 掌握程度：🌟🌟🌟

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

给你一个有序数组 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 * 104 -104 <= nums[i] <= 104 nums 已按升序排列

解题思路

相对 26. 删除有序数组中的重复项 - 力扣（LeetCode） 来说困难点在没个元素最多出现两次,思路基本一致，通过双指针来进行一 次遍历，遍历过程中对元素进行 swap 操作，来满足时间和空间复杂度的要求

首先我们维护两个指针 slow , fast , 当重复元素超过 2 个时，我们交换 fast slow 所在的元素， 直到 fast 迭代到 nums 的尾部时结束循环，现在看看如何处理重复元素这一个问题如果我们在去考虑维护一个计数器来记录次数，但是换种思路来看，数组是有序的，如果是 [1,1,1,2,2,3] 这个 case ，我们只需要判断 nums[slow-2] 是否与当前元素一致即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length < 2){
            return nums.length;
        }
        int slow = 2;
        int fast = 2;
        while(fast < nums.length){
            if(nums[slow-2] != nums[fast]){
                  swap(nums,slow,fast);
                  slow++;
            }
            fast++;
        }
        return slow;
    }
    private void swap(int[] nums,int x ,int y){
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}