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