मान लीजिए कि हमें मेडियनक्लास नामक एक वर्ग को लागू करना है जिसमें निम्नलिखित तरीके शामिल हैं -
-
add(value) जो डेटा संरचना में एक मान जोड़ता है।
-
माध्य () डेटा संरचना में वर्तमान में मौजूद सभी संख्याओं का माध्यिका ढूँढता है।
इसलिए, यदि हम 5, 3, 8 जोड़ते हैं और माध्यिका पाते हैं, तो आउटपुट 5.0 होगा, फिर यदि हम 9 जोड़ते हैं और माध्यिका पाते हैं, तो आउटपुट 6.5 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
प्राथमिकता कतार को बाएँ और दाएँ परिभाषित करें
-
AddNum विधि को परिभाषित करें, यह संख्या को इनपुट के रूप में लेगा -
-
यदि बायां खाली है या संख्या <बाएं का शीर्ष तत्व है, तो,
-
बाईं ओर संख्या डालें
-
-
अन्यथा
-
संख्या को दाईं ओर डालें
-
-
यदि बाएँ का आकार <दाएँ का आकार है, तो,
-
अस्थायी:=दाईं ओर का शीर्ष तत्व
-
आइटम को दाईं ओर से हटाएं
-
बाईं ओर अस्थायी डालें
-
-
यदि बाएँ का आकार - दाएँ का आकार> 1, तो,
-
अस्थायी:=बाईं ओर का शीर्ष तत्व
-
बाईं ओर से आइटम हटाएं
-
दाईं ओर अस्थायी डालें
-
-
FindMedian() विधि को परिभाषित करें, यह इस प्रकार कार्य करेगा -
बाएं के शीर्ष पर लौटें यदि बाएं का आकार> दाएं का आकार, अन्यथा (बाएं का शीर्ष + दाएं का शीर्ष) / 2 बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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;
}
};
main(){
MedianClass ob;
ob.addNum(5);
ob.addNum(3);
ob.addNum(8);
cout << ob.findMedian() << " ";
ob.addNum(9);
cout << ob.findMedian() << endl;
} इनपुट
ob.addNum(5); ob.addNum(3); ob.addNum(8); cout << ob.findMedian() << endl; ob.addNum(9); cout << ob.findMedian() << endl;
आउटपुट
5.0 6.5
