इस समस्या में, हमें इंटीजर्स का एक ऐरे और एक इंटीजर K दिया गया है। हमारा कार्य एक ऐसा प्रोग्राम बनाना है जो बिना डुप्लिकेट के आकार K के प्रत्येक सबऐरे में अधिकतम अद्वितीय एलिमेंट ढूंढे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट −
array = {4, 1, 1, 3, 3} k = 3आउटपुट −
4 3 1
व्याख्या −
आकार 3 का सब-ऐरे सबऐरे {4, 1, 1}, अधिकतम = 4 सबऐरे {1, 1, 3}, अधिकतम = 3 सबऐरे {1, 3, 3}, अधिकतम = 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
