用时 : 看了答案
既然是堆的练习,肯定是往堆的思路去靠拢了
由于我们要的仅仅是中位数,其实没有必要把所有的数都排序
可以用两个堆,一个最大堆一个最小堆
当总数为单数(即 最大堆 - 最小堆 个数 = 1),拿到最大堆的最大值
当总数为双数(即最大堆个数 = 最小堆) ,拿到最大堆最大值和最小堆最小值
1 | const swap = function (arr,i,j) { |
需要注意的点
- 为了保证最大堆 个数 - 最小堆 为 0 ~ 1,且最大堆的最大值 < 最小堆 的最小值,每次数先进入最大堆,然后最大堆把最大值传递给最小堆。再根据数量判断是否把最小堆的最小值给最大堆
- 只实现了最大堆,但是可以用负数来做最小堆,出的时候别忘了也要负数