C++ এ ডেটা স্ট্রিম থেকে মিডিয়ান খুঁজুন

ধরুন আমাদের একটি ডাটা স্ট্রীম আছে, সেই স্ট্রীমে কিছু ডাটা এলিমেন্ট এসে যোগ দিতে পারে, আমাদের একটা সিস্টেম তৈরি করতে হবে, যেটা ডাটা থেকে মিডিয়ান বের করতে সাহায্য করবে। আমরা জানি যে মধ্যমা হল একটি বাছাই করা তালিকার মধ্যম ডেটা, যদি এটি তালিকার দৈর্ঘ্য বিজোড় হয়, তাহলে আমরা সরাসরি মধ্যমা পেতে পারি, অন্যথায় মধ্যম দুটি উপাদান গ্রহণ করুন, তারপর গড় বের করুন। সুতরাং দুটি পদ্ধতি থাকবে, addNum() এবং findMedian(), এই দুটি পদ্ধতি স্ট্রীমে সংখ্যা যোগ করতে এবং সমস্ত যোগ করা সংখ্যার মধ্যক খুঁজে বের করতে ব্যবহার করা হবে

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

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

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

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

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

• অন্যথায়

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

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

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

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

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

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

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

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

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

• 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