এই সমস্যায়, আমাদের একটি n আকারের অ্যারে এবং একটি সংখ্যা M দেওয়া আছে। আমাদের কাজ হলো একটি প্রোগ্রাম তৈরি করা যা নির্দিষ্ট আকারের সাব-অ্যারেতে সর্বোচ্চ অনন্য পূর্ণসংখ্যা বের করবে।
এখানে আমাদের M আকারের সাব-অ্যারেটি খুঁজে বের করতে হবে যেটিতে সর্বোচ্চ অনন্য উপাদান রয়েছে।
সমস্যা বুঝতে নিচের উদাহরণটি দেখুন,
ইনপুট − অ্যারে = {4, 1, 2, 1 , 4, 3}. M = 4
আউটপুট − 4
ব্যাখ্যা −
আকার ৪-এর সকল সম্ভাব্য সাব-অ্যারে কম্বিনেশন: {4, 1, 2, 1} = ৩টি অনন্য উপাদান {1, 2, 1, 4} = ৩টি অনন্য উপাদান {2, 1, 4, 3} = ৪টি অনন্য উপাদানএই সমস্যা সমাধানের জন্য, আমরা সাধারণভাবে M আকারের সকল সাব-অ্যারে তৈরি করে প্রতিটিতে অনন্য উপাদান গণনা করব। এবং অনন্য উপাদানের সংখ্যা গ্লোবাল সর্বোচ্চের চেয়ে বড় কিনা তা যাচাই করে সর্বোচ্চ মানটি সংরক্ষণ করব। কিন্তু এই সমাধান দক্ষ নয়।
একটি ভালো সমাধান হলো স্লাইডিং উইন্ডো টেকনিক ব্যবহার করা। এতে আমরা M আকারের একটি উইন্ডো তৈরি করি এবং বর্তমান উইন্ডোর অনন্য উপাদানগুলো সংরক্ষণের জন্য একটি হ্যাশ টেবিল ব্যবহার করব।
উইন্ডোটি নিচেরভাবে তৈরি করব −
M আকারের একটি উইন্ডো তৈরি করে উপাদানগুলো হ্যাশ ম্যাপে সংরক্ষণ করুন।
এরপর উইন্ডোটি (M+1) তম উপাদানের অবস্থানে সরিয়ে προηγের উইন্ডোর উপাদানটি বাদ দিন।
উদাহরণ থেকে এই সমাধানটি ভালোভাবে বুঝতে নিচের টেবিলটি দেখুন −
অ্যারে = {4, 1, 2, 1, 4, 3}
উইন্ডো আকার, M = 4.
| উইন্ডো | হ্যাশ ম্যাপ | অনন্য উপাদানের সংখ্যা | যোগ করা উপাদান | বাদ দেওয়া উপাদান |
| {4,1,2,1} | 4,1,2 | 3 | - | - |
| {1,2,1,4} | 1,2,4 | 3 | 4 | 4 |
| {2,1,4,3} | 2,1,4,3 | 4 | 3 | 1 |
এই সমাধানটি দেখাচ্ছে উইন্ডো এবং হ্যাশ ম্যাপ কীভাবে গঠিত হয় এবং অনন্য উপাদান কীভাবে গণনা করা হয়।
উদাহরণ
নির্দিষ্ট আকারের সাব-অ্যারেতে সর্বোচ্চ অনন্য পূর্ণসংখ্যা বের করার প্রোগ্রাম −
#include<bits/stdc++.h> using namespace std; int maxUniqueElement(int a[],int N,int M){ map<int,int> hashMap; int uniqueCountWindow=0; int uniqueCount=0; for(int i=0;i<M;i++) { if(hashMap.find(a[i])==hashMap.end()) { hashMap.insert(make_pair(a[i],1)); uniqueCountWindow++; } else hashMap[a[i]]++; } uniqueCount = uniqueCountWindow; for(int i=M;i<N;i++) { if(hashMap[a[i-M]]==1) { hashMap.erase(a[i-M]); uniqueCountWindow--; } else hashMap[a[i-M]]--; if(hashMap.find(a[i])==hashMap.end()){ hashMap.insert(make_pair(a[i],1)); uniqueCountWindow++; } else hashMap[a[i]]++; uniqueCount=max(uniqueCount,uniqueCountWindow); } return uniqueCount; } int main(){ int arr[] = {4, 1 ,2, 1, 4, 3}; int M=4; int N=sizeof(arr)/sizeof(arr[0]); cout<<"The maximum number of unique elements in sub-array of size "<<M<<" is "<<maxUniqueElement(arr,N,M)<<endl; }আউটপুট
The maximum number of unique elements in sub-array of size 4 is 4
