মান লইয়া আমাদের একটি ক্লাস ইমপ্লিমেন্ট করতে হবে নামক MedianClass যাতে নিচের মেথডগুলো থাকে:
add(value)যা ডেটা স্ট্রাকচারে একটি ভ্যালু অ্যাড করে।median()যা ডেটা স্ট্রাকচারে বর্তমানে উপস্থিত সব সংখ্যার মিডিয়ান বের করে।
তবে, যদি আমরা 5, 3, 8 অ্যাড করি এবং মিডিয়ান বের করি, আউটপুট হবে 5.0, তারপর যদি 9 অ্যাড করি এবং মিডিয়ান বের করি, আউটপুট হবে 6.5।
এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:
- প্রায়োরিটি কিউ
leftএবংrightডিফাইন করুন addNumমেথড ডিফাইন করুন, এটি নম্বর ইনপুট হিসেবে নেবে:- যদি left খালি থাকে বা num < left-এর টপ এলিমেন্ট, তবে num left-এ ইনসার্ট করুন
- অন্যথায় num right-এ ইনসার্ট করুন
- যদি left-এর সাইজ < right-এর সাইজ, তবে right-এর টপ left-এ মুভ করুন
- যদি left-এর সাইজ - right-এর সাইজ > 1, তবে left-এর টপ right-এ মুভ করুন
findMedian()মেথড ডিফাইন করুন:- left-এর টপ রিটার্ন করুন যদি left-এর সাইজ > right-এর সাইজ, অন্যথায় (left-এর টপ + right-এর টপ) / 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
