凡客诚品上一年度市场份额_微信小程序卖货_seo赚钱方法大揭秘_百度问答平台

原题地址：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，要求移除重复元素，使得每个元素最多只出现两次。返回移除重复元素后的新数组长度。

2. 双指针法：

   • 本题采用 双指针法，通过两个指针来扫描和处理数组。
     • 慢指针 (slow)：指向新数组的位置（即有效元素的数组下标），它会随着我们找到有效元素而移动。
     • 快指针 (fast)：遍历整个数组，尝试找到不重复的元素。
   • 主要的思路是允许每个元素出现最多两次。如果当前元素与前面两个元素不同，则将当前元素赋给慢指针指向的位置，并移动慢指针。如果当前元素与前面两个元素相同，则跳过该元素（快指针继续前进）。
   • 这样，慢指针所指的部分就是最终的去重后的数组，返回慢指针的下标即为新数组的长度。

源码实现

class Solution {public int removeDuplicates(int[] nums) {// 如果数组为空或者长度为0，直接返回0if (nums == null || nums.length == 0) {return 0;}// 如果数组长度小于3，则直接返回数组的长度，因为最多能保留两次重复元素if (nums.length < 3) {return nums.length;}// 慢指针和快指针初始化为2，因为前两个元素最多出现两次int slow = 2, fast = 2;// 快指针从第三个元素开始遍历整个数组while (fast < nums.length) {// 如果当前元素与前两个元素不同，则可以将当前元素放入慢指针的位置if (nums[slow - 2] != nums[fast]) {nums[slow] = nums[fast];++slow; // 移动慢指针}// 快指针继续前进++fast;}// 返回新数组的长度，即慢指针的位置return slow;}
}

复杂度分析

1. 时间复杂度：

   • 由于我们只遍历了一遍数组，且每次操作常数时间，所以时间复杂度是 O(n)，其中 n 是数组的长度。

2. 空间复杂度：

   • 由于我们只用了常数空间来保存慢指针和快指针，因此空间复杂度是 O(1)。