C++で指定されたサイズのサブ配列内の一意の整数の最大数

この問題では、サイズnと数値Mの配列が与えられます。私たちのタスクは、サブで一意の整数の最大数を見つけるプログラムを作成することです。指定されたサイズの配列。

ここでは、一意の要素の数が最大であるサイズMのサブ配列を見つける必要があります。

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

入力 −配列={4、1、2、1、4、3}。 M =4

出力 − 4

説明 −

All possible combinations of sub-arrays of size 4.
{4, 1, 2, 1} = 3 unique elements
{1, 2, 1, 4} = 3 unique elements
{2, 1, 4, 3} = 4 unique elements

この問題を解決するには、サイズMのすべてのサブ配列を生成してから、サブ配列内の一意の要素の数を数えます。そして、一意の要素の数がグローバルな最大一意の要素数よりも多いかどうかを確認し、両方の最大値を格納します。しかし、このソリューションは効率的ではありません。

より良い解決策は、スライディングウィンドウ手法を使用することです。ここでは、サイズmのウィンドウを作成し、ハッシュテーブルを使用して現在のウィンドウの一意の要素を格納します。

次の方法でウィンドウを作成します-

• サイズMのウィンドウを作成し、要素をハッシュマップに保存します。

• 次に、（M + 1）の位置にある要素のウィンドウに移動し、前のウィンドウの要素を削除します。

ソリューションをよりよく理解するために、この例からこのソリューションを見てみましょう-

配列={4、1、2、1、4、3}

ウィンドウサイズ、M=4。

このソリューションは、ウィンドウとハッシュマップがどのように形成され、一意の要素の数がカウントされるかを示しています 。

例

指定されたサイズのサブ配列内の一意の整数の最大数を見つけるプログラム-

#include<bits/stdc++.h>
using namespace std;
int maxUniqueElement(int a[],int N,int M){
   map<int,int> hashMap;
   int uniqueCountWindow=0;
   int uniqueCount=0;
   for(int i=0;i<M;i++) {
      if(hashMap.find(a[i])==hashMap.end()) {
         hashMap.insert(make_pair(a[i],1));
         uniqueCountWindow++;
      }
      else
         hashMap[a[i]]++;
      }
      uniqueCount = uniqueCountWindow;
      for(int i=M;i<N;i++) {
         if(hashMap[a[i-M]]==1) {
            hashMap.erase(a[i-M]);
            uniqueCountWindow--;
         }
         else
            hashMap[a[i-M]]--;
            if(hashMap.find(a[i])==hashMap.end()){
               hashMap.insert(make_pair(a[i],1));
               uniqueCountWindow++;
            }
            else
               hashMap[a[i]]++;
               uniqueCount=max(uniqueCount,uniqueCountWindow);
         }
      return uniqueCount;
}
int main(){
   int arr[] = {4, 1 ,2, 1, 4, 3};
   int M=4;
   int N=sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum number of unique elements in sub-array of size "<<M<<" is "<<maxUniqueElement(arr,N,M)<<endl;
}

出力

The maximum number of unique elements in sub-array of size 4 is 4