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

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.
【分析】
この問題の鍵は、余分なスペースを利用せずに数値の削除を完了することです.そのため、既存のスペース、すなわち入力データが存在するスペースでしかデータを操作できません.問題の意味によって、重複を除去したデータを順次元の配列の前に並べる必要があるので、データの移動操作は避けられない.移動データについては、一般的に2つの方案がある:1、全体の移動、問題が指す重複データに遍歴した後、私たちはその後ろのデータを全体的に1位移動して、重複データをカバーする.最悪の場合,入力した配列n個のデータはすべて同じであり,[(n−3)+(n−4)+...+0]を移動する必要があり,nが比較的大きい場合,時間複雑度はO(n 2)であった.2、「ダブルポインタ」は、1つのポインタが配列を巡回することを担当し、1つのポインタは常に次の重複データのない格納位置を指し、逐次移動し、時間の複雑度はO(n)である.
【解法及び注釈】
分析によると、私は2つの方法のプログラムをテストしました.効率の差は多くありません.これはテストケースのデータ規模の比較と関係があるかもしれません.
方法1:

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

方法2:

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