# 1825. Finding MK Average ###### tags: `Leetcode` `Hard` `Design` Link: https://leetcode.com/problems/finding-mk-average/description/ ## 思路 思路参考[这里](https://github.com/wisdompeak/LeetCode/tree/master/Heap/1825.Finding-MK-Average)和[这里](https://leetcode.com/problems/finding-mk-average/solutions/1152742/clean-java-with-3-treemaps/) 我们维护三个treemap left, mid, right size分别为k, m-2k, k 我们还维护一个linkedlist 这样我们可以找到应该要删除的元素 先删掉一个元素 假设删掉的元素值为num, 我们跟left的最大的元素比，如果比它小，说明我们从left删，如果比right最小的元素大，我们从right里面删，否则从mid里面删 然后我们加一个num 同样是跟left的最大和right的最小比 看放在哪里 接着开始shift 我们可以写两个shift函数 shiftLeft(A,B) 把B里面最小的拿去A里面 shiftRight(A,B) 把A里面最大的拿去B里面