C++でソート済み配列から重複を削除する方法(各要素は最大2回まで許容)

ソートされた配列 nums が与えられたとき、同じ要素が最大2回まで現れるように、配列自体を書き換える形(インプレース)で重複を削除し、新しい長さを返すことを考えます。

この問題の重要な制約は、追加のメモリを使用できないという点です。つまり、O(1)の追加領域だけで解決しなければなりません。

例えば、入力配列が [0,0,0,1,1,1,1,2,3,3] の場合、出力は [0,0,1,1,2,3,3] となり、新しい長さは 7 になります。

アルゴリズムの考え方

この問題は「二ポインタ(書き込み位置と読み取り位置)」を使うテクニックで効率的に解けます。ポイントは、既に確定した末尾2つの要素と比較することで、「3連続以上の重複」を防ぐことです。

手順

• 書き込み位置 len を 2 に初期化し、配列サイズを n とします。
• n <= 2 の場合は、どの要素も削除不要なのでそのまま n を返します。
• i = 2 から n - 1 までループします。
  • nums[i] が nums[len - 2] または nums[len - 1] のいずれかと異なる場合(= まだ2連続になっていない場合)、nums[len] = nums[i] としてコピーし、len を1増やします。
• 最後に len を返します。

この方法なら、各要素は時間計算量 O(n)、追加空間 O(1) で処理できます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int removeDuplicates(vector<int>& nums) {
      int len = 2;
      int n = nums.size();
      if(n <= 2)return n;
      for(int i = 2; i < n; i++){
         if( nums[i] != nums[len - 2] || nums[i] != nums[len - 1]){
            nums[len] = nums[i];
            len++;
         }
      }
      return len;
   }
};
main(){
   Solution ob;
   vector<int> v = {0,0,0,1,1,1,1,2,3,3};
   cout << ob.removeDuplicates(v);
}

入力

[0,0,0,1,1,1,1,2,3,3]

出力

7

まとめ

このアルゴリズムでは、配列の先頭2要素は必ず残るため len を 2 から開始し、3番目以降の要素について「直前に確定した2要素との比較」を行うことで、同一要素が3回以上連続して現れるのを防いでいます。条件式で OR(||)を使っているため、直前2つのうちどちらか一方でも異なればその要素を採用でき、正しく「最大2回まで」というルールを実現できます。