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

怼烎@ 2023-09-28 14:18 31阅读 0赞

####  ####

*  题目描述
 *  思路
 *  流程图
 *  代码

## 题目描述 ##

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

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

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

## 思路 ##

这道题目其实就是说，数组中如果存在重复元素的话，那么这个元素只能出现两次。像这种原地修改的题目，很容易就想到双指针

*  慢指针 slow : 指向当前即将放置元素的位置；则 slow - 1 是刚才已经放置了元素的位置。
 *  快指针 fast : 向后遍历所有元素；
 *   所以让 nums\[fast\] 跟 nums\[slow - 2\] 进行比较。每次都是只允许最多两个元素出现重复，这两个元素的位置在 slow - 1 和 slow - 2.
 *  从题目我们可以分析得出，前两个元素肯定是要保留下来的

## 流程图 ##

![在这里插入图片描述][69b9f219f91048dba0b0e33f60afb285.png]  
![在这里插入图片描述][e666394f54f146b2a22ffa31035f7511.png]

![在这里插入图片描述][3371290c64f24799af0f9f6d71eaacf3.png]  
![在这里插入图片描述][fa2a2ce58a1241319fa02bfa785b044b.png]  
![在这里插入图片描述][aecde4390b714172802d595a1efd4ca6.png]

## 代码 ##

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

[LeetCode80. _ II]: https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii
[69b9f219f91048dba0b0e33f60afb285.png]: https://img-blog.csdnimg.cn/69b9f219f91048dba0b0e33f60afb285.png
[e666394f54f146b2a22ffa31035f7511.png]: https://img-blog.csdnimg.cn/e666394f54f146b2a22ffa31035f7511.png
[3371290c64f24799af0f9f6d71eaacf3.png]: https://img-blog.csdnimg.cn/3371290c64f24799af0f9f6d71eaacf3.png
[fa2a2ce58a1241319fa02bfa785b044b.png]: https://img-blog.csdnimg.cn/fa2a2ce58a1241319fa02bfa785b044b.png
[aecde4390b714172802d595a1efd4ca6.png]: https://img-blog.csdnimg.cn/aecde4390b714172802d595a1efd4ca6.png