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

บทนำ

ในบทช่วยสอนนี้ เราจะสร้างคลาส MedianClass ที่รองรับ 2 การดำเนินการ:

• add(value) - เพิ่มค่าเข้าไปในโครงสร้างข้อมูล
• median() - หาค่ามัธยฐานของตัวเลขทั้งหมดที่เพิ่มไปแล้ว

ตัวอย่างการใช้งาน

add(5), add(3), add(8) → median() = 5.0
add(9) → median() = 6.5

อัลกอริทึม: Two Heaps (Priority Queues)

ใช้ 2 Priority Queue:

• left (max-heap): เก็บครึ่งล่างของข้อมูล (ค่าน้อยกว่า median)
• right (min-heap): เก็บครึ่งบนของข้อมูล (ค่ามากกว่า median)

ขั้นตอนการทำงาน

1. เพิ่มค่า: ถ้า left ว่างหรือค่า < top(left) → push เข้า left, ไป right
2. Rebalance: ถ้า left < right → ย้าย top(right) ไป left
3. Rebalance: ถ้า left > right + 1 → ย้าย top(left) ไป right
4. หา median: ถ้า left > right → top(left), ไป (top(left)+top(right))/2

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

typedef double lli;

class MedianClass {
    priority_queue left;  // max-heap
    priority_queue, greater> right;  // min-heap
    
public:
    void addNum(int num) {
        if (left.empty() || num < left.top()) {
            left.push(num);
        } else {
            right.push(num);
        }
        
        // Rebalance
        if (left.size() < right.size()) {
            int temp = right.top();
            right.pop();
            left.push(temp);
        }
        if (left.size() - right.size() > 1) {
            int temp = left.top();
            left.pop();
            right.push(temp);
        }
    }
    
    double findMedian() {
        return left.size() > right.size() ? left.top() : (left.top() + right.top()) * 0.5;
    }
};

int main() {
    MedianClass ob;
    ob.addNum(5);
    ob.addNum(3);
    ob.addNum(8);
    cout << ob.findMedian() << " ";  // 5.0
    ob.addNum(9);
    cout << ob.findMedian() << endl;  // 6.5
    return 0;
}

ผลลัพธ์

5.0 6.5

ความซับซ้อน

• addNum: O(log n)
• findMedian: O(1)
• พื้นที่: O(n)

สรุป

Two Heaps technique เป็นวิธีมาตรฐานในการหา median แบบ streaming/online หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ