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;
}
}