C++でサイズKのすべての部分配列における最大の一意要素を効率的に求める方法

この問題では、整数の配列と整数Kが与えられます。私たちの課題は、サイズKの各部分配列の中で、重複して現れない要素(一意な要素)のうち最大値を見つけるプログラムを作成することです。

まず、具体的な例を使って問題を理解しましょう。

入力 −

array = {4, 1, 1, 3, 3}
k = 3

出力 −

4 3 1

説明 −

サイズ3の部分配列を順に調べる
部分配列 {4, 1, 1} の場合、一意な要素は {4}、最大値 = 4
部分配列 {1, 1, 3} の場合、一意な要素は {3}、最大値 = 3
部分配列 {1, 3, 3} の場合、一意な要素は {1}、最大値 = 1

問題を解くアプローチ

この問題を解く最も単純な方法は、2重ループを使ってすべての部分配列を生成し、それぞれの一意な要素を調べてその最大値を出力することです。しかし、この方法の計算量はO(N×K)となり、配列が大きくなると非効率になります。

そこで有効なのが、ハッシュテーブルと自己平衡二分探索木(BST)を組み合わせたスライディングウィンドウ法です。

アルゴリズムの流れ

配列を走査しながら、サイズKのウィンドウを1つずつスライドさせていきます。

• ハッシュテーブル(map)で、ウィンドウ内の各要素の出現回数を管理します。
• セット(set)には、ウィンドウ内でちょうど1回だけ出現する要素(一意な要素)のみを格納します。
• 各ウィンドウごとに、セット内の最大値(rbegin()で取得)を出力します。
• ウィンドウがスライドする際は、右端に新しい要素を追加し、左端から古い要素を削除します。このとき出現回数の変化に応じて、セットの内容も適切に更新します。
• 一意な要素が1つも存在しない場合は「-1」を出力します。

この手法により、各ステップの更新処理をO(log K)で行えるため、全体を効率的に処理できます。

実装例

上記の解法を実装したプログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
void maxUniqueSubArrayElement(int A[], int N, int K){
   map<int, int> eleCount;
   for (int i = 0; i < K - 1; i++)
      eleCount[A[i]]++;
   set<int> uniqueMax;
   for (auto x : eleCount)
      if (x.second == 1)
         uniqueMax.insert(x.first);
   for (int i = K - 1; i < N; i++) {
      eleCount[A[i]]++;
      if (eleCount[A[i]] == 1)
          uniqueMax.insert(A[i]);
      else
         uniqueMax.erase(A[i]);
      if (uniqueMax.size() == 0)
         cout<<"-1\t" ;
      else
         cout<<*uniqueMax.rbegin()<<"\t";
      int x = A[i - K + 1];
      eleCount[x]--;
      if (eleCount[x] == 1)
         uniqueMax.insert(x);
      if (eleCount[x] == 0)
         uniqueMax.erase(x);
   }
}
int main(){
   int a[] = { 4, 3, 2, 2, 3, 5};
   int n = sizeof(a) / sizeof(a[0]);
   int k = 4;
   cout<<"The maximum unique element for a subarray of size "<<k<<" is\n";
      maxUniqueSubArrayElement(a, n, k);
   return 0;
}

出力

The maximum unique element for a subarray of size 4 is 4 -1 5

このプログラムでは、配列 {4, 3, 2, 2, 3, 5} からサイズ4の部分配列を順番に調べています。最初の部分配列 {4, 3, 2, 2} では一意な要素が4と3のうち最大の4、次の {3, 2, 2, 3} では一意な要素が存在しないため-1、最後の {2, 2, 3, 5} では一意な要素が3と5のうち最大の5が出力されます。

計算量について

この解法の時間計算量はO(N log K)です。各要素の追加・削除がセットに対してO(log K)で完了するため、単純な2重ループによるO(N×K)の手法と比べて大幅に高速です。空間計算量はO(K)となります。