【LeetCode】80. Remove Duplicates from Sorted Array II解法及注释

￡神魔★判官ぃ 2022-07-26 11:27 15阅读 0赞

80. Remove Duplicates from Sorted Array II

Total Accepted: 71844 Total Submissions: 220521 Difficulty: Medium

Follow up for "Remove Duplicates":  
What if duplicates are allowed at most twice?

For example,  
Given sorted array nums = `[1,1,1,2,2,3]`,

Your function should return length = `5`, with the first five elements of nums being `1`, `1`, `2`, `2` and `3`. It doesn't matter what you leave beyond the new length.

【分析】

此题的关键在于不利用额外空间而完成数字的删除，因此，我们只能在现有空间，也就是输入数据所在的空间对数据进行操作。根据题意，我们需要将去除重复后的数据依次排在原数组的前面，因此，不可免要对数据进行移动操作，关于移动数据，一般有**两种方案**：1、**整体移动**，当遍历到题目所指的重复数据后，我们将其后面的数据整体移动一位，从而将重复数据覆盖，如此，最糟糕的情况，输入的数组n个数据全相同，我们需要移动\[(n-3)+(n-4)+...+0\],当n比较大时，时间复杂度为O(n2)；2、**“双指针”**，一个指针负责遍历数组，一个指针始终指向下一个无重复数据的存放位置，逐次移动，时间复杂度为O(n).

【解法及注释】

根据分析，我将两种方法的程序均进行了测试，效率相差不多，这可能与测试案例的数据规模比较有关。

**方法一：**

class Solution33 {
    public:
        int removeDuplicates(vector<int>& nums) {
            
            if(nums.size()<3)return nums.size();
            int result=1;//记录删除重复后的数据长度
            int count=0;//标记重复
            int move=0;//移动次数
            
            for(int i=0;i<nums.size()-1;)
            {
                if(nums[i]>nums[i+1])//原数组是排序的，每次遇到重复，就将其移动到数组的末尾，其后的数据则前移1位
                {                    //因此，数组尾部的数据会比原数组尾部的数据小，这个特点可以作为判断遍历完成的条件
                   break;
                }
                else if(nums[i]!=nums[i+1])//相邻元素不等
                {
                    result++;
                    count=0;
                    i++;//控制循环
                    move=0;
                }
                else if(nums[i]==nums[i+1])//相邻数据相等
                {
                    if(count==2)//已经重复（超过2）
                    {
                        count=2;
                        move++;//记录移动次数
                        int temp=nums[i+1];//把重复数据移动到数组尾部
                        for(int k=i+1;k<nums.size()-1;k++)//整体前移
                        {
                            nums[k]=nums[k+1];
                        }
                        nums[nums.size()-1]=temp;//交换到尾部
                        if(move>nums.size()-i-2)//避免陷入死循环
                        i++;
                    }
                    else //该数据两次出现
                    {
                        count=2;//标记
                        result++;//记录
                        i++;//进入下一次循环
                        move=0;
                    }
                }
            }
            return result;
            
        }
    };

**方法二：**

class Solution {
    public:
        int removeDuplicates(vector<int> &nums) 
        {
            if(nums.size() < 3) return nums.size();
            int length = 1;
            int flag = 1;//标记重复（超过2次）
            
            for(int i = 1; i < nums.size(); i++)
            {
                if(nums[i] != nums[i-1])//相邻数据不等，将数据存储到length指向的空间
                {
                    nums[length++] = nums[i];
                    flag = 1;//标记
                }
                else if(flag == 1)//出现相等数据，且与之前的数据不等
                {
                    nums[length++] = nums[i];//将数据存储到length指向的空间
                    flag++;//标记改变
                }
                else//出现相等数据，且之前已经出现了2个，因此i指向的数据不是期望的数据，不保存
                    continue;
            }
            return length;
        }
    };