โปรแกรมหาค่ามัธยฐานของอาร์เรย์จำนวนเต็มใน C++

สมมติว่าเราต้องใช้คลาสชื่อ MedianClass ซึ่งมีวิธีการดังต่อไปนี้ -

• add(value) ซึ่งเพิ่มมูลค่าให้กับโครงสร้างข้อมูล

• ค่ามัธยฐาน () ค้นหาค่ามัธยฐานของตัวเลขทั้งหมดที่มีอยู่ในโครงสร้างข้อมูลในปัจจุบัน

ดังนั้น หากเราบวก 5, 3, 8 และหาค่ามัธยฐาน ผลลัพธ์จะเป็น 5.0 จากนั้นหากเราบวก 9 และหาค่ามัธยฐาน ผลลัพธ์จะเป็น 6.5

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

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

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

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

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

• มิฉะนั้น

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

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

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

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

  • ใส่ temp ไปทางซ้าย

• ถ้าขนาดของด้านซ้าย − ขนาดด้านขวา> 1 แล้ว

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

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

  • ใส่อุณหภูมิด้านขวา

• กำหนดเมธอด findMedian() ซึ่งจะทำหน้าที่ดังนี้ -

return top of left if size of left> size of right, else (บนซ้าย + บนขวา)/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