C++ में एक पूर्णांक सरणी की माध्यिका ज्ञात करने का कार्यक्रम

मान लीजिए कि हमें मेडियनक्लास नामक एक वर्ग को लागू करना है जिसमें निम्नलिखित तरीके शामिल हैं -

• 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