मान लीजिए हमारे पास एक डेटा स्ट्रीम है, उस स्ट्रीम में कुछ डेटा तत्व आ सकते हैं और जुड़ सकते हैं, हमें एक सिस्टम बनाना है, जो डेटा से मेडियन ढूंढने में मदद करेगा। जैसा कि हम जानते हैं कि मेडियन एक क्रमबद्ध सूची का मध्य डेटा है, यदि सूची की लंबाई विषम है, तो हम सीधे मेडियन प्राप्त कर सकते हैं, अन्यथा मध्य के दो तत्व लें, फिर औसत ढूंढें। तो दो विधियां होंगी, addNum() और findMedian(), इन दो विधियों का उपयोग संख्याओं को स्ट्रीम में जोड़ने के लिए, और सभी जोड़ी गई संख्याओं का मेडियन ढूंढने के लिए किया जाएगा
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
प्राथमिकता कतार left और right परिभाषित करें
addNum विधि परिभाषित करें, जो संख्या को इनपुट के रूप में लेगी -
यदि left खाली है या num < left का शीर्ष तत्व, तो,
num को left में डालें
अन्यथा
num को right में डालें
यदि left का आकार < right का आकार, तो,
temp := right का शीर्ष तत्व
right से आइटम हटाएं
temp को left में डालें
यदि left का आकार - right का आकार > 1, तो,
temp := left का शीर्ष तत्व
left से आइटम हटाएं
temp को right में डालें
findMedian() विधि परिभाषित करें, यह निम्नानुसार कार्य करेगी -
यदि left का आकार > right का आकार तो left का शीर्ष लौटाएं, अन्यथा (left का शीर्ष + right का शीर्ष)/2
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; typedef double lli; class MedianFinder { 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; } }; main(){ MedianFinder ob; ob.addNum(10); ob.addNum(15); cout << ob.findMedian() << endl; ob.addNum(25); ob.addNum(30); cout << ob.findMedian() << endl; ob.addNum(40); cout << ob.findMedian(); }इनपुट
addNum(10); addNum(15); findMedian(); addNum(25); addNum(30); findMedian(); addNum(40); findMedian();
आउटपुट
12.5 20 25