【附JS、C++、Python题解】LeetCode 面试150题（4）

一、题目

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

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

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

二、思路

看到题目以后，我们先思考一下这道题与26. 删除有序数组中的重复项的联系。

• 相同点：都是“原地删除“，”有序数组“（上一道题具体到了非严格递增），“重复元素”；
• 不同点：返回值不同（意味着我们定义的变量含义也不同），要求的结果不同（出现次数超过两次的元素保留两个而不是一个，可以看成，这里的重复标准就是出现次数大于2）。
• 特别要求：不使用额外的数组空间，等于是再次强调了“原地”。

1. 基于相同点，我们有以下思路：

• 还是要用双指针；
• 还是要判断重复情况；

2. 基于不同点，有以下思路：

• 数组新长度基于原长度变化，只需要用表达式表达出变化规律（类似于在某个循环下执行完某一步长度+1）；
• 重复标准由1变2，基本逻辑不会有大的改动；

总的来说，我们还是可以使用两个指针来解决这个问题：

1. 快指针（fast）：用于遍历整个数组，找到所有“唯二”的元素。
2. 慢指针（slow）：用于标记唯二元素的位置，并在原地修改数组。

三、步骤

1. 初始化指针 slow 为 2，因为前两个元素无论是否重复都保留；

2. 快指针 fast 从数组的第三个元素开始遍历，首先判断当前元素是否与慢指针前两个位置的元素不同；

3. 当当前元素的重复次数不超过 2 次时，将该元素放到慢指针 slow 所指向的位置，并移动慢指针；当重复次数超过 2 次时，跳过该元素。

4. 遍历结束后，慢指针 slow 的值即为删除重复元素后数组的新长度。

四、代码

① JavaScript代码：

function deleteSame(nums){
    if(nums.length <= 2){
        return nums.length;
    }
    let slow = 2;
    for(let fast=2; fast<nums.length; fast++){
        if(nums[fast] !== nums[slow-2]){
            nums[slow] = nums[fast];
            slow ++;
        }
    }
    return slow;
}

② python代码：

def deletSame(nums):
    if len(nums) <= 2:
        return len(nums)
    slow = 2
    for fast in range(2,len(nums)):
        if nums[fast] != nums[slow-2]:
            nums[slow] = nums[fast]
            slow += 1
    return slow

③ C++代码：

int deleteSum(vector <int> &nums){
    int length = nums.size();
    if( length<=2){
        return length;
    }
    int slow = 2;
    for (int fast =2;fast<length;fast++){
        if(nums[fast] != nums[slow-2]){
            nums[slow] = nums[fast];
            slow ++;
        }
    } 
    return slow;
}

五、思路整理

1. 初始化 slow 指针：

• slow 指针从第三个元素开始（索引为 2），因为前两个元素肯定是允许的。

2. 遍历数组：

• 使用 fast 指针从第三个元素开始遍历数组。

• 如果 nums[fast] 和 nums[slow - 2] 不同，说明当前元素是一个新的元素，或者是允许的重复元素。

• 将 nums[fast] 赋值给 nums[slow]，并移动 slow 指针。

3. 返回新长度：

• 最终 slow 指针的位置就是删除重复元素后的数组长度。