C++ में दिए गए आकारों के उप-सरणी में अद्वितीय पूर्णांकों की अधिकतम संख्या

इस समस्या में, हमें आकार n और एक संख्या M की एक सरणी दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो उप-में अद्वितीय पूर्णांकों की अधिकतम संख्या ज्ञात करेगा। दिए गए आकार की सरणी।

यहां, हमें आकार M की उप-सरणी ढूंढनी होगी जिसमें अद्वितीय तत्वों की अधिकतम संख्या हो।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट - सरणी ={4, 1, 2, 1 , 4, 3}। एम =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}

खिड़की का आकार, एम =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