ค่าเฉลี่ยของ K ตัวเลขมากที่สุดในสตรีมข้อมูล C++

ปัญหา

ให้อาร์เรย์เริ่มต้น และสตรีมข้อมูลที่เข้ามาเรื่อยๆ ต้องการคำนวณค่าเฉลี่ยของ K ตัวเลขที่มากที่สุดในแต่ละขั้นตอน

ตัวอย่าง: n=4, k=3, arr=[4,9,1,5], stream=[2,6,3,7]

• เริ่มต้น: 3 ตัวมากที่สุดคือ 9,5,4 → ค่าเฉลี่ย = 6
• เพิ่ม 2: ไม่เข้า top 3 → ค่าเฉลี่ย = 6
• เพิ่ม 6: แทนที่ 4 → top 3 คือ 9,6,5 → ค่าเฉลี่ย = 6.67
• เพิ่ม 3: ไม่เข้า top 3 → ค่าเฉลี่ย = 6.67
• เพิ่ม 7: แทนที่ 5 → top 3 คือ 9,7,6 → ค่าเฉลี่ย = 7.33

วิธีแก้ปัญหา: Min Heap

ใช้ Min Heap ขนาด K เก็บ K ตัวมากที่สุด:

1. สร้าง Min Heap จาก K ตัวมากที่สุดของอาร์เรย์เริ่มต้น
2. เก็บผลรวมของสมาชิกใน Heap
3. สำหรับแต่ละค่าในสตรีม:
   • ถ้าค่าใหม่ > root ของ Heap (ค่าน้อยที่สุดใน top K) → แทนที่ root
   • อัปเดตผลรวม
   • คำนวณค่าเฉลี่ย = sum / k

ความซับซ้อน: O(n log k + m log k) โดย m = จำนวนข้อมูลในสตรีม

ตัวอย่างโค้ด C++ (ใช้ priority_queue)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

void maxAverageKNumbers(int n, int k, vector<int>& arr, vector<int>& stream) {
    // Min heap
    priority_queue<int, vector<int>, greater<int>> pq;
    double sum = 0;
    
    // เรียงอาร์เรย์และใส่ k ตัวมากที่สุด
    sort(arr.begin(), arr.end());
    for (int i = n - 1; i >= n - k; i--) {
        pq.push(arr[i]);
        sum += arr[i];
    }
    
    cout << fixed << setprecision(2);
    for (int val : stream) {
        if (val > pq.top()) {
            sum -= pq.top();
            pq.pop();
            pq.push(val);
            sum += val;
        }
        cout << "Average: " << (sum / k) << endl;
    }
}

int main() {
    vector<int> arr = {4, 9, 1, 5};
    vector<int> stream = {2, 6, 3, 7};
    int n = 4, k = 3;
    maxAverageKNumbers(n, k, arr, stream);
    return 0;
}

ผลลัพธ์

Average: 6.00
Average: 6.67
Average: 6.67
Average: 7.33