leetcode 41数据流中的中位数

Java 使用 PriorityQueue<>((x, y) -> (y - x)) 可方便实现大顶堆。

Java 使用 PriorityQueue<>() 可方便实现小顶堆。

一般思路

• 先排序再进行再遍历取数
• 使用 O(Nlog⁡N)时间，然后返回中间元素即可（使用 O(1)时间）。

进一步优化

　　使用大小顶堆实现数据动态的堆内有序，A小顶堆保存数值较大的部较小的部分。

• add函数：

　　如果是AB大小相等，说明A要增加，但是通过将num加到B，再将B栈顶元素进行poll加入到A

　　如果是AB大小不等，说明B要增加，但是通过将num加到A，再将A栈顶元素进行poll加入到B

• find：

　　注意除法中分子括号，如果AB数目不等则peek A反之求平均。

改进之后时空复杂度：

• 时间复杂度：O(logN) ：(这里可以和leetcode40对比，可以发现往堆里面更新数据为logN，由于40题是对于K个数进行更新所以用logK)
  
• 空间复杂度 ：O(N)：其中其中 NN 为数据流中的元素数量，小顶堆 AA 和大顶堆 BB 最多同时保存 NN 个元素。