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