C++のサイズKのすべてのサブ配列の最大一意要素

この問題では、整数の配列と整数Kが与えられます。私たちのタスクは、サイズKのすべてのサブ配列で重複のない最大の一意の要素を見つけるプログラムを作成することです。

問題を理解するために例を見てみましょう

入力 −

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

出力 −

4 3 1

説明 −

Sub-array of size 3
Subarray {4, 1, 1}, max = 4
Subarray {1, 1, 3}, max = 3
Subarray {1, 3, 3}, max = 1

この問題を解決する簡単な方法の1つは、2つのループを実行してサブ配列を作成し、個別の要素を見つけて最大数を出力することです。

ただし、効果的な解決策は、スライディングウィンドウ方式を使用することです。 ハッシュテーブルと自己平衡BSTを使用して、最大の要素を見つけます。

したがって、配列をトラバースし、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