ค้นหาค่ามัธยฐานจาก Data Stream ใน C++

สมมติว่าเรามี data Stream ในสตรีมนั้นองค์ประกอบข้อมูลบางอย่างอาจมารวมกัน เราต้องสร้างระบบเดียว ที่จะช่วยค้นหาค่ามัธยฐานจากข้อมูล ดังที่เรารู้ว่าค่ามัธยฐานเป็นข้อมูลตรงกลางของรายการที่จัดเรียง หากความยาวของรายการเป็นเลขคี่ เราสามารถหาค่ามัธยฐานได้โดยตรง มิฉะนั้น ให้เอาองค์ประกอบตรงกลางสององค์ประกอบ แล้วหาค่าเฉลี่ย ดังนั้นจะมีสองวิธีคือ addNum() และ findMedian() ทั้งสองวิธีนี้จะใช้เพื่อเพิ่มตัวเลขลงในสตรีม และหาค่ามัธยฐานของตัวเลขที่เพิ่มทั้งหมด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดลำดับความสำคัญของคิวซ้ายและขวา

• กำหนดวิธี addNum ซึ่งจะใช้ตัวเลขเป็นอินพุต -

• ถ้า left ว่างหรือ num <องค์ประกอบบนของ left แล้ว

  • ใส่ num เข้าไปทางซ้าย

• มิฉะนั้น

  • ใส่ num เข้าไปทางขวา

• ถ้าขนาดซ้าย <ขนาดขวา แล้ว

  • temp :=องค์ประกอบด้านบนของด้านขวา

  • ลบรายการออกจากด้านขวา

  • ใส่ 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