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

이 문제를 해결하기 위한 간단한 방법 중 하나는 두 개의 루프를 실행하고 하위 배열을 만들고 고유한 요소를 찾아 최대값으로 인쇄하는 것입니다.

그러나 효과적인 해결책은 슬라이딩 창 방식을 사용하는 것입니다. 해시 테이블과 자체 균형 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