LeetCode80. 删除有序数组中的重复项 II

小咪咪 2022-11-16 04:57 189阅读 0赞

难度：中等  
题目描述：

> 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。  
> 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]解题思路：

> 因为给定数组是有序的，所以相同元素必然连续。我们可以使用双指针解决本题，遍历数组检查每一个元素是否应该被保留，如果应该被保留，就将其移动到指定位置。  
> 我们定义两个指针 slow和 fast 分别为慢指针和快指针，其中慢指针表示处理出的数组的长度，快指针表示已经检查过的数组的长度，即nums\[fast\] 表示待检查的第一个元素，nums\[slow−1\] 为上一个应该被保留的元素所移动到的指定位置。
> 
> 因为本题要求相同元素最多出现两次而非一次，所以我们需要检查上上个应该被保留的元素 nums\[slow−2\] 是否和当前待检查元素nums\[fast\] 相同。当且仅当 nums\[slow−2\] =nums\[fast\] 时，当前待检查元素 nums\[fast\]不应该被保留  
> （因为此时必然有 nums\[slow−2\]=nums\[slow−1\]=nums\[fast\])。  
> 最后，slow 即为处理好的数组的长度。  
> 特别地，数组的前两个数必然可以被保留，因此对于长度不超过 2的数组，我们无需进行任何处理，对于长度超过 222 的数组，我们直接将双指针的初始值设为 2 即可。

class Solution { 
    public:
        int removeDuplicates(vector<int>& nums) { 
            int n=nums.size();
            if(n<3){ 
                return n;
            }
            int slow=2,fast=2;
            while(fast<n){ 
                if(nums[slow-2]!=nums[fast]){ 
                    nums[slow]=nums[fast];
                    slow++;
                }
                fast++;
            }
            return slow;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221022/1c209b9899dd4410acd5790c11e0f80a.png