इस समस्या में, हमें पूर्णांकों की एक सरणी और एक पूर्णांक 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