HardRating 2396

1825. Finding MK Average

designqueueheap-priority-queuedata-streamordered-set

解題說明

Finding MK Average

題目描述：設計一個資料結構，維護最近 m 個元素的串流。支持 addElement(num) 新增元素和 calculateMKAverage() 計算 MK 平均值：取最近 m 個元素，去掉最小的 k 個和最大的 k 個，回傳剩餘元素的平均值（取整）。

解題思路：使用三個有序多重集合（multiset）維護最小的 k 個、中間的 m-2k 個、最大的 k 個元素。新增元素時先判斷應插入哪個集合，然後調整平衡。同時用佇列記錄插入順序，當元素超過 m 個時移除最早的元素。維護中間集合的元素總和以快速計算平均值。

C++ 解法

複雜度分析

時間複雜度：O(log m)（每次 addElement）— multiset 的插入和刪除為 O(log m)。calculateMKAverage 為 O(1)。

空間複雜度：O(m) — 三個 multiset 和佇列共儲存 m 個元素。

虛擬碼

1. Maintain three multisets: lo (k smallest), mid (middle m-2k), hi (k largest)
2. Maintain midSum = sum of elements in mid
3. addElement(num):
   a. Push to queue
   b. Insert into lo, rebalance to mid and hi if sizes exceed k / m-2k
   c. If queue size > m: remove oldest element, rebalance sets
4. calculateMKAverage():
   a. If queue size < m, return -1
   b. Return midSum / (m - 2k)

其他解法

排序陣列 + 滑動窗口：維護最近 m 個元素的排序陣列，每次新增/移除後用二分搜索插入/刪除。時間 O(m) 每次操作（元素位移），空間 O(m)。簡單但較慢。

BIT（樹狀陣列）：用 BIT 維護元素計數和前綴和，支持 O(log V) 的第 k 小查詢和區間和計算。適合值域較小的情況。

延伸思考

若 k 是動態變化的（每次查詢可能不同），如何設計？
若要支持刪除任意元素（不只是最舊的），資料結構如何修改？
若串流是分佈式的（多個來源），如何合併計算 MK Average？

Finding MK Average — CaffeCode