C++ এ প্রদত্ত আকারের সাব-অ্যারেতে অনন্য পূর্ণসংখ্যার সর্বাধিক সংখ্যা

এই সমস্যায়, আমাদেরকে n আকারের একটি অ্যারে এবং একটি সংখ্যা M দেওয়া হয়েছে। আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা উপ-এ সর্বাধিক সংখ্যক অনন্য পূর্ণসংখ্যা খুঁজে পাবে। প্রদত্ত আকারের অ্যারে।

এখানে, আমাদেরকে M আকারের সাব-অ্যারে খুঁজে বের করতে হবে যেখানে সর্বাধিক সংখ্যক অনন্য উপাদান রয়েছে।

সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,

ইনপুট − অ্যারে ={4, 1, 2, 1, 4, 3}। M =4

আউটপুট − 4

ব্যাখ্যা −

All possible combinations of sub-arrays of size 4.
{4, 1, 2, 1} = 3 unique elements
{1, 2, 1, 4} = 3 unique elements
{2, 1, 4, 3} = 4 unique elements

এই সমস্যাটি সমাধান করার জন্য, আমরা কেবল M আকারের সমস্ত সাববারে তৈরি করব এবং তারপর সাব্যারেতে অনন্য উপাদানের সংখ্যা গণনা করব। এবং অনন্য উপাদানের সংখ্যা বিশ্বব্যাপী সর্বাধিক অনন্য উপাদান গণনার চেয়ে বেশি কিনা তা পরীক্ষা করুন এবং উভয়ের মধ্যে সর্বশ্রেষ্ঠটি সংরক্ষণ করুন। কিন্তু এই সমাধান কার্যকর নয়।

একটি ভাল সমাধান স্লাইডিং উইন্ডো কৌশল ব্যবহার করা হবে. যেটিতে আমরা m আকারের একটি উইন্ডো তৈরি করি এবং তারপরে বর্তমান উইন্ডোর জন্য অনন্য উপাদান সংরক্ষণের জন্য একটি হ্যাশ টেবিল ব্যবহার করি।

আমরা নিম্নলিখিত উপায়ে উইন্ডোটি তৈরি করব -

• M আকারের একটি উইন্ডো তৈরি করুন এবং উপাদানগুলিকে একটি হ্যাশ মানচিত্রে সংরক্ষণ করুন৷

• তারপরে (M+1) অবস্থানে থাকা উপাদানটির জন্য উইন্ডোতে যান এবং পূর্ববর্তী উইন্ডোটির জন্য উপাদানটি সরান৷

সমাধানটি আরও ভালভাবে বুঝতে আমাদের উদাহরণ থেকে এই সমাধানটি দেখা যাক -

অ্যারে ={4, 1, 2, 1, 4, 3}

জানালার আকার, M =4.

এই সমাধানটি দেখায় কিভাবে উইন্ডো এবং হ্যাশ ম্যাপ তৈরি হয় এবং অনন্য উপাদানের সংখ্যা গণনা করা হয় .

উদাহরণ

প্রদত্ত আকারের সাব-অ্যারেতে সর্বাধিক সংখ্যক অনন্য পূর্ণসংখ্যা খুঁজে পাওয়ার প্রোগ্রাম -

#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