1825. 求出MK平均值Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你两个整数 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⁵
1 <= k*2 < m
1 <= num <= 10⁵
addElement 与 calculateMKAverage 总操作次数不超过 10⁵ 次。

# 思路

TreeMap

# 解法

class MKAverage {

    public final int m;
    public final int k;
    public int sum;
    public Queue<Integer> queue;
    public TreeMap<Integer, Integer> map;

    public MKAverage(int m, int k) {
        this.m = m;
        this.k = k;
        this.queue = new LinkedList<>();
        map = new TreeMap<>();
    }
    
    public void addElement(int num) {
        if (queue.size() == m) {
            Integer poll = queue.poll();
            if (map.get(poll) == 1) {
                map.remove(poll);
            } else {
                map.put(poll, map.get(poll) - 1);
            }
            sum -= poll;
        }
        queue.add(num);
        sum += num;
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    
    public int calculateMKAverage() {
        int size = queue.size();
        if (size < m) {
            return -1;
        }
        return (sum - getSum(map.entrySet().iterator()) - getSum(map.descendingMap().entrySet().iterator())) / (m - 2 * k);
    }

    private int getSum(Iterator<Map.Entry<Integer, Integer>> iterator) {
        int i = k, keySum = 0;
        while (i > 0) {
            Map.Entry<Integer, Integer> next = iterator.next();
            int val = Math.min(next.getValue(), i);
            i -= val;
            keySum += next.getKey() * val;
        }

        return keySum;
    }
}

/**
 * Your MKAverage object will be instantiated and called as such:
 * MKAverage obj = new MKAverage(m, k);
 * obj.addElement(num);
 * int param_2 = obj.calculateMKAverage();
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

# 总结

分析出几种情况，然后分别对各个情况实现

#Java