C++ का उपयोग करके N रेंज में अधिकतम घटित होने वाला पूर्णांक

समस्या विवरण

इस समस्या में, हमें N रेंज दी गई हैं। हमारा कार्य N रेंज में अधिकतम घटित होने वाला पूर्णांक खोजना है।

सभी रेंज के प्रारंभिक और अंतिम मान के लिए। हमें वह मान खोजने की आवश्यकता है जो सबसे अधिक बार आता है।

उदाहरण

इनपुट

S1 = 1, E1 = 3
S2 = 2, E2 = 6
S3 = 3, E3 = 4

आउटपुट

3

व्याख्या: 3 रेंज [1,3], [2,6], [3,4] में आता है (3 बार), जो अधिकतम है।

हल का दृष्टिकोण

समस्या को हल करने का एक सरल दृष्टिकोण हैशिंग का उपयोग करना है। हम सभी सदस्यों और उनकी गिनती को गिनने के लिए एक हैश टेबल का उपयोग करेंगे। हम सभी रेंज को पार करेंगे और हैश टेबल में गिनती संग्रहीत करेंगे, फिर हम अधिकतम गिनती खोजेंगे।

रैखिक समय में समस्या को हल करने का एक अन्य दृष्टिकोण रेंज सरणी (डिफरेंस सरणी / प्रीफिक्स योग तकनीक) का उपयोग करना है। इस सरणी में, हम सभी रेंज के प्रारंभ मानों के इंडेक्स को 1 जोड़कर और सभी रेंज के अंत मानों के इंडेक्स से 1 घटाकर अपडेट करेंगे। फिर प्रीफिक्स योग खोजेंगे और अधिकतम प्रीफिक्स योग मान खोजेंगे।

एल्गोरिदम (डिफरेंस सरणी दृष्टिकोण)

1. पर्याप्त रूप से बड़ी सरणी freq[] को 0 से प्रारंभ करें
2. प्रत्येक रेंज [L[i], R[i]] के लिए:
   • freq[L[i]]++
   • freq[R[i] + 1]--
3. freq[] का प्रीफिक्स योग 계산 करें
4. अधिकतम प्रीफिक्स योग वाला इंडेक्स उत्तर है

C++ कार्यान्वयन

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

int findMaxOccrEle(int L[], int R[], int n) {
    vector<int> occurrenceCount(MAX, 0);
    int maxi = -1;
    
    for (int i = 0; i < n; i++) {
        occurrenceCount[L[i]] += 1;
        if (R[i] + 1 < MAX)
            occurrenceCount[R[i] + 1] -= 1;
        if (R[i] > maxi) {
            maxi = R[i];
        }
    }
    
    int prefSum = occurrenceCount[0];
    int maxEleIndex = 0;
    
    for (int i = 1; i <= maxi; i++) {
        occurrenceCount[i] += occurrenceCount[i - 1];
        if (prefSum < occurrenceCount[i]) {
            prefSum = occurrenceCount[i];
            maxEleIndex = i;
        }
    }
    
    return maxEleIndex;
}

int main() {
    int L[] = {1, 2, 3};
    int R[] = {3, 6, 4};
    int n = sizeof(L) / sizeof(L[0]);
    cout << "रेंज में अधिकतम घटित होने वाला पूर्णांक है " << findMaxOccrEle(L, R, n);
    return 0;
}

आउटपुट

रेंज में अधिकतम घटित होने वाला पूर्णांक है 3

जटिलता विश्लेषण

• समय जटिलता: O(n + MAX_VALUE) जहां MAX_VALUE अधिकतम रेंज अंत बिंदु है
• स्पेस जटिलता: O(MAX_VALUE)

टिप्पणी

डिफरेंस सरणी तकनीक बड़ी रेंज के लिए हैशिंग की तुलना में अधिक कुशल है क्योंकि यह O(1) रेंज अपडेट और O(MAX) अंतिम गणना की अनुमति देती है।