---
# System prepended metadata

title: 1825. Finding MK Average
tags: [Leetcode, Design, Hard]

---

# 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里面