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?