【2023-01-18每日一题】1825. 求出 MK 平均值[Hard]
2023-01-18
2分钟阅读时长
2023-01-18每日一题：1825. 求出 MK 平均值
难度：Hard
标签：设计 、 队列 、 数据流 、 有序集合 、 堆（优先队列）
给你两个整数 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 <= 1051 <= k*2 < m1 <= num <= 105addElement与calculateMKAverage总操作次数不超过105次。
方法一：
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
type MKAverage struct {
}
func Constructor(m int, k int) MKAverage {
}
func (this *MKAverage) AddElement(num int) {
}
func (this *MKAverage) CalculateMKAverage() int {
}
/**
* Your MKAverage object will be instantiated and called as such:
* obj := Constructor(m, k);
* obj.AddElement(num);
* param_2 := obj.CalculateMKAverage();
*/