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

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

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

आइए एक उदाहरण से इस समस्या को समझते हैं,

इनपुट - array = {4, 1, 2, 1, 4, 3}. M = 4

आउटपुट - 4

व्याख्या -

आकार 4 के सभी संभावित सब-ऐरे संयोजन। 
{4, 1, 2, 1} = 3 अद्वितीय तत्व 
{1, 2, 1, 4} = 3 अद्वितीय तत्व 
{2, 1, 4, 3} = 4 अद्वितीय तत्व

इस समस्या को हल करने के लिए, हम बस आकार M के सभी सबऐरे उत्पन्न करेंगे और फिर सबऐरे में अद्वितीय तत्वों की संख्या गिनेंगे। और जांचेंगे कि क्या अद्वितीय तत्वों की संख्या ग्लोबल अधिकतम अद्वितीय तत्व गणना से अधिक है, और दोनों में से सबसे बड़ा स्टोर करेंगे। लेकिन यह समाधान कुशल नहीं है।

एक बेहतर समाधान स्लाइडिंग विंडो तकनीक का उपयोग करना होगा। जिसमें हम आकार m की एक विंडो बनाते हैं और फिर वर्तमान विंडो के लिए अद्वितीय तत्वों को स्टोर करने के लिए एक हैश टेबल का उपयोग करते हैं।

हम निम्न तरीके से विंडो बनाएंगे -

• आकार M की एक विंडो बनाएं और तत्वों को हैश मैप में स्टोर करें।

• फिर (M+1) स्थिति पर तत्व के लिए विंडो को मूव करें और पिछली विंडो के तत्व को हटा दें।

आइए इस समाधान को हमारे उदाहरण से देखें ताकि समाधान बेहतर समझ में आए -

Array = {4, 1, 2, 1, 4, 3}

विंडो आकार, M = 4.

यह समाधान दिखाता है कि विंडो और हैश मैप कैसे बनते हैं और अद्वितीय तत्वों की गणना कैसे की जाती है।

उदाहरण

दिए गए आकार के सब-ऐरे में अद्वितीय पूर्णांकों की अधिकतम संख्या ढूंढने का प्रोग्राम -

#include<bits/stdc++.h> 
using namespace std; 

int maxUniqueElement(int a[], int N, int M) {
    map 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