LeetCode[中等] 80. 删除有序数组中的重复项 II

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

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

 

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

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。双指针各遍历数组一次。

• 空间复杂度：O(1)。

More

这道题要求删除数组中重复出现的元素，使每个元素最多出现两次。上述做法可以推广到更普遍的情形，即对于任意 x≥1，删除数组中重复出现的元素，使每个元素最多出现 x 次。

对于普遍的情形，做法是首先判断数组长度是否大于 x，如果数组长度小于等于 x 则返回数组长度，如果数组长度大于 x 则使用双指针。

初始时将快指针 fast 和 slow 都指向下标 x，判断当前元素是否为重复元素时比较 nums[fast] 和 nums[slow−x] 是否相等，其余逻辑不变。时间复杂度和空间复杂度与上述做法相同。

下面的代码为这道题在普遍情形下的实现，取 x=2 的特例。

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