文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你兩個整數 m 和 k ，以及數據流形式的若干整數。
你需要實現一個數據結構，計算這個數據流的 MK 平均值 。

MK 平均值 按照如下步驟計算：

• 如果數據流中的整數少于 m 個，MK 平均值 為 -1 ，否則將數據流中最后 m 個元素拷貝到一個獨立的容器中。
• 從這個容器中刪除最小的 k 個數和最大的 k 個數。
• 計算剩余元素的平均值，并 向下取整到最近的整數 。

請你實現 MKAverage 類：

• MKAverage(int m, int k) 用一個空的數據流和兩個整數 m 和 k 初始化 MKAverage 對象。
• void addElement(int num) 往數據流中插入一個新的元素 num 。
• int calculateMKAverage() 對當前的數據流計算并返回 MK 平均數 ，結果需 向下取整到最近的整數 。

示例 1： 輸入： ["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"] [[3, 1], [3], [1], [], [10], [], [5], [5], [5], []] 輸出： [null, null, null, -1, null, 3, null, null, null, 5] 解釋： MKAverage obj = new MKAverage(3, 1); obj.addElement(3); // 當前元素為 [3] obj.addElement(1); // 當前元素為 [3,1] obj.calculateMKAverage(); // 返回 -1 ，因為 m = 3 ，但數據流中只有 2 個元素 obj.addElement(10); // 當前元素為 [3,1,10] obj.calculateMKAverage(); // 最后 3 個元素為 [3,1,10]// 刪除最小以及最大的 1 個元素后，容器為 [3]// [3] 的平均值等于 3/1 = 3 ，故返回 3 obj.addElement(5); // 當前元素為 [3,1,10,5] obj.addElement(5); // 當前元素為 [3,1,10,5,5] obj.addElement(5); // 當前元素為 [3,1,10,5,5,5] obj.calculateMKAverage(); // 最后 3 個元素為 [5,5,5]// 刪除最小以及最大的 1 個元素后，容器為 [5]// [5] 的平均值等于 5/1 = 5 ，故返回 5提示： 3 <= m <= 10^5 1 <= k*2 < m 1 <= num <= 10^5 addElement 與 calculateMKAverage 總操作次數不超過 10^5 次。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/finding-mk-average
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 使用 3個 multiset 記錄3段數據，同時queue記錄數據，更新刪除，只保留 m 個
• 記錄 中間段的 sum

class MKAverage {int m, k;long long sum = 0;//中間的數的和queue<int> q;multiset<int> big, mid;multiset<int, greater<int>> small; public:MKAverage(int m, int k) {this->m = m;this->k = k;}void addElement(int num) {if(q.size() < m){q.push(num);big.insert(num);//插入大的里面process();//處理3個set，保持有序，以及控制數量}else//滿了{int tp = q.front();q.pop();q.push(num);big.insert(num);//插入大的里面if(mid.find(tp) != mid.end()){sum -= tp;mid.erase(mid.find(tp));}else if(big.find(tp) != big.end())big.erase(big.find(tp));else // (small.find(tp) != small.end())small.erase(small.find(tp));process();//處理3個set，保持有序，以及控制數量}}void process(){ // 處理 3個 setwhile(big.size() > k){ // big 滿了， 小的 放到 small 里small.insert(*big.begin());big.erase(big.begin());}while(small.size() > k){ // small 滿了，大的放到 mid 里mid.insert(*small.begin());sum += *small.begin(); // mid 和 增加small.erase(small.begin());}if(big.size()+mid.size()+small.size() < m)return;//數量不夠 m 個， 結束邏輯if(*big.begin() < *mid.rbegin()){ // 大的最小的 小于 中間的最大的， 交換數值int v1 = *mid.rbegin(), v2 = *big.begin();sum += v2-v1;mid.erase(--mid.end());big.erase(big.begin());mid.insert(v2);big.insert(v1);}if(big.size() < k){ // 大的數量不夠，中間的挪一個最大的到 大的auto it = --mid.end();sum -= *it;big.insert(*it);mid.erase(it);}if(*small.begin() > *mid.begin()){ // 小的最大的 大于 中間最小的，交換數值int v1 = *mid.begin(), v2 = *small.begin();sum += v2-v1;mid.erase(mid.begin());small.erase(small.begin());mid.insert(v2);small.insert(v1);}if(small.size() < k){ // 小的數量不夠，中間挪一個最小的到 小的auto it = mid.begin();sum -= *it;small.insert(*it);mid.erase(it);}}int calculateMKAverage() {if(q.size() < m)return -1;return sum/(m-2*k);} };

560 ms 156.9 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1825. 求出 MK 平均值（set + queue）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。