এই সমস্যায়, আমাদেরকে পূর্ণসংখ্যার একটি অ্যারে এবং একটি পূর্ণসংখ্যা 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
