C++ में पूर्णांक सरणी का माध्यिका (Median) ढूंढने का प्रोग्राम

परिचय

मान लीजिए हमें MedianClass नामक एक क्लास लागू करनी है जिसमें निम्नलिखित मेथड्स हों:

• add(value) जो डेटा संरचना में एक मान जोड़ता है।
• median() वर्तमान में डेटा संरचना में मौजूद सभी संख्याओं का माध्यिका ढूंढता है।

तो, यदि हम 5, 3, 8 जोड़ते हैं और माध्यिका ढूंढते हैं, तो आउटपुट 5.0 होगा, फिर यदि हम 9 जोड़ते हैं और माध्यिका ढूंढते हैं, तो आउटपुट 6.5 होगा।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम दो प्रायोरिटी क्यू (हीप) का उपयोग करते हैं:

• एक मैक्स-हीप (left) छोटे आधे तत्वों के लिए
• एक मिन-हीप (right) बड़े आधे तत्वों के लिए

हम दोनों हीप्स को संतुलित रखते हैं ताकि उनके आकार में अंतर अधिकतम 1 हो।

उदाहरण कोड

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

typedef double lli;

class MedianClass {
    priority_queue<int> left;  // मैक्स हीप
    priority_queue<int, vector<int>, greater<int>> right;  // मिन हीप
    
public:
    void addNum(int num) {
        if(left.empty() || num < left.top()){
            left.push(num);
        } else {
            right.push(num);
        }
        if(left.size() < right.size()){
            lli temp = right.top();
            right.pop();
            left.push(temp);
        }
        if(left.size() - right.size() > 1){
            lli temp = left.top();
            left.pop();
            right.push(temp);
        }
    }
    
    double findMedian() {
        return left.size() > right.size() ? left.top() : (left.top() + right.top()) * 0.5;
    }
};

int main(){
    MedianClass ob;
    ob.addNum(5);
    ob.addNum(3);
    ob.addNum(8);
    cout << ob.findMedian() << " ";
    ob.addNum(9);
    cout << ob.findMedian() << endl;
    return 0;
}

इनपुट

ob.addNum(5); ob.addNum(3); ob.addNum(8); cout << ob.findMedian() << endl; ob.addNum(9); cout << ob.findMedian() << endl;

आउटपुट

5.0 6.5

व्याख्या

[5,3,8] के लिए सॉर्टेड: [3,5,8], माध्यिका = 5

[5,3,8,9] के लिए सॉर्टेड: [3,5,8,9], माध्यिका = (5+8)/2 = 6.5

निष्कर्ष

दो हीप्स का उपयोग करके स्ट्रीमिंग डेटा के लिए माध्यिका O(log n) प्रति इंसर्शन में निकाली जा सकती है। यह दृष्टिकोण बड़े डेटा स्ट्रीम के लिए कुशल है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।