题目
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入： ["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出:[null,null,2.00000,null,2.50000]</pre>
限制：
- 最多会对
addNum、findMedia进行50000次调用。
注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/
解法
现在想要维持的结构是一直知道中位数在哪里，最直观的思路就是用排序的数组或者链表，让数据一直保持有序。
但是显然，这样做太重了，毕竟我只需要知道中位数的位置就好，两边的数字不需要有序，所以思路就是，把数据分成两边：
左边是比较小的数，但是右边界要比左边的都大；
右边是比较大的数，但是左边界要比右边的数都大。
显然左半边用一个大根堆，右半边用小根堆，输入数据时候维持两边一样多，中间的就是中位数。
1 5 4 3 2 6 | | 7 12 14 13 9 8
为了维持右半边整体比左半边大，可以插入堆后再pop出来，得到最大（最小）值。
class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.minHeap = []
# 用最小堆实现，插入取出的时候都取负数
self.maxHeap = []
def addNum(self, num: int) -> None:
if len(self.minHeap) == len(self.maxHeap) :
num = -heapq.heappushpop(self.maxHeap,-num)
heapq.heappush(self.minHeap, num)
else:
num = heapq.heappushpop(self.minHeap,num)
heapq.heappush(self.maxHeap, -num)
def findMedian(self) -> float:
if len(self.minHeap) == len(self.maxHeap):
return (self.minHeap[0] - self.maxHeap[0])/2
else:
return self.minHeap[0]
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
总结
heapq没有大根堆，用负数进去负数出来的方式。
插入数字的时候要pushpop才能保证右边小根堆最小的都比大根堆要大。
用两个堆数量是否相等判断奇偶，来决定插入哪个。
两个中位数取平均值。
网友评论