C++에서 주어진 크기의 하위 배열에 있는 고유 정수의 최대 수

이 문제에서 크기가 n이고 숫자가 M인 배열이 주어집니다. 우리의 임무는 Sub-에서 고유한 정수의 최대 수를 찾는 프로그램을 만드는 것입니다. 주어진 크기의 배열.

여기에서 최대 고유 요소 수를 갖는 크기 M의 하위 배열을 찾아야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - 배열 ={4, 1, 2, 1, 4, 3}. 남 =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