C++ এ একটি পূর্ণসংখ্যা অ্যারের মধ্যমা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের মিডিয়ানক্লাস নামের একটি ক্লাস বাস্তবায়ন করতে হবে যাতে নিম্নলিখিত পদ্ধতিগুলি রয়েছে -

• add(value) যা ডেটা স্ট্রাকচারে একটি মান যোগ করে।

• median() বর্তমানে ডেটা স্ট্রাকচারে উপস্থিত সমস্ত সংখ্যার মধ্যক খুঁজে বের করে।

সুতরাং, যদি আমরা 5, 3, 8 যোগ করি এবং মধ্যমা খুঁজে পাই, তাহলে আউটপুট হবে 5.0, তারপর যদি আমরা 9 ​​যোগ করি এবং মধ্যমা খুঁজে পাই, তাহলে আউটপুট হবে 6.5।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• বাম এবং ডান অগ্রাধিকার সারি সংজ্ঞায়িত করুন

• addNum পদ্ধতি সংজ্ঞায়িত করুন, এটি সংখ্যাটিকে ইনপুট হিসাবে গ্রহণ করবে −

• যদি বামটি খালি হয় বা num হয় <বামের শীর্ষ উপাদান, তারপর,

  • বাম দিকে সংখ্যা সন্নিবেশ করান

• অন্যথায়

  • ডানদিকে সংখ্যা প্রবেশ করান

• যদি বামের আকার <ডানের আকার, তাহলে,

  • temp :=ডানদিকের শীর্ষ উপাদান

  • ডান থেকে আইটেম মুছুন

  • বাম দিকে তাপমাত্রা সন্নিবেশ করুন

• যদি বামের মাপ − ডানের সাইজ> 1, তারপর,

  • temp :=বাম দিকের শীর্ষ উপাদান

  • বাম থেকে আইটেম মুছুন

  • ডানদিকে তাপমাত্রা সন্নিবেশ করুন

• 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