解题思路
维护 3 个 multiset:lower(保存最小的 kkk 个数)、middle(中间的数)、upper(保存最大的 kkk 个数)。
插入操作
·如果 num≤max(lower),则在 lower中插入 num
·如果 num≥min(upper),则在 upper 中插入 num
·否则,在 middle 中插入 num
如果插入后,lower 或 upper 中的元素多于 k 个,则向 middle 中 转移 元素
操作过程中维护 middle 的元素和 sum
删除操作
·设删除的元素为 d
·d 一定存在于 lower 或middle 或 upper 中的一个或多个集合中
·择一删除即可
如果删除后,lower 或 upper 中的元素少于 k 个,则从 middle 中 索取 元素
操作过程中维护 middle 的元素和 sum
平均值操作
平均值 = sum/(m−2⋅k)sum / (m - 2\cdot k)sum/(m−2⋅k) (向下取整)。
有问题的代码:
1 | class MKAverage: |