मान लीजिए कि हमारे पास एक डेटा स्ट्रीम है, उस स्ट्रीम में कुछ डेटा तत्व आ सकते हैं और जुड़ सकते हैं, हमें एक सिस्टम बनाना होगा, जो डेटा से माध्यिका को खोजने में मदद करेगा। जैसा कि हम जानते हैं कि माध्यिका क्रमबद्ध सूची का मध्य डेटा है, यदि सूची की लंबाई विषम है, तो हम सीधे माध्यिका प्राप्त कर सकते हैं, अन्यथा मध्य दो तत्व लें, फिर औसत ज्ञात करें। तो दो विधियाँ होंगी, addNum () और findMedian (), इन दो विधियों का उपयोग संख्याओं को स्ट्रीम में जोड़ने के लिए किया जाएगा, और सभी जोड़े गए नंबरों का माध्यिका ज्ञात करें
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
प्राथमिकता कतार को बाएँ और दाएँ परिभाषित करें
-
AddNum विधि को परिभाषित करें, यह संख्या को इनपुट के रूप में लेगा -
-
यदि बायां खाली है या संख्या <बाएं का शीर्ष तत्व है, तो,
-
बाईं ओर संख्या डालें
-
-
अन्यथा
-
संख्या को दाईं ओर डालें
-
-
यदि बाएँ का आकार <दाएँ का आकार है, तो,
-
अस्थायी:=दाईं ओर का शीर्ष तत्व
-
आइटम को दाईं ओर से हटाएं
-
बाईं ओर अस्थायी डालें
-
-
यदि बाएँ का आकार – दाएँ का आकार> 1, तो,
-
अस्थायी:=बाईं ओर का शीर्ष तत्व
-
बाईं ओर से आइटम हटाएं
-
दाईं ओर अस्थायी डालें
-
-
FindMedian() विधि को परिभाषित करें, यह इस प्रकार कार्य करेगा -
-
बाएं के शीर्ष पर लौटें यदि बाएं का आकार> दाएं का आकार, अन्यथा (बाएं का शीर्ष + दाएं का शीर्ष)/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