ফাইন্ড মেডিয়ান ফ্রম ডেটা স্ট্রিম
একটি ডেটা স্ট্রিমে সংখ্যাগুলো এক এক করে আসছে। দুটি অপারেশন সমর্থন করতে হবে:
addNum(num): সংখ্যা যোগ করুনfindMedian(): বর্তমান সব সংখ্যার মেডিয়ান ফেরত দিন
মেডিয়ান = সর্ট করা তালিকার মধ্যবর্তী মান (বিজোড় দৈর্ঘ্যে) বা দুটি মধ্যবর্তী মান গড় (জোড় দৈর্ঘ্যে)।
সমাধানের পদ্ধতি (দুটি হিপ / Two Heaps)
- ম্যাক্স হিপ
left: ছোট অর্ধেক রাখে (রুট = বড়তম) - মিন হিপ
right: বড় অর্ধেক রাখে (রুট = ছোটতম) - সainte করুন:
left.size() == right.size()বাleft.size() == right.size() + 1 addNum: উপযুক্ত হিপে যোগ করুন, তারপর রিব্যালেন্স করুনfindMedian:left.top()বা(left.top() + right.top())/2
C++ কোড উদাহরণ
addNum(10); addNum(15); findMedian(); addNum(25); addNum(30); findMedian(); addNum(40); findMedian();
আউটপুট
12.5 20 25
