面试题41. 数据流中的中位数

题目

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[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才能保证右边小根堆最小的都比大根堆要大。
用两个堆数量是否相等判断奇偶，来决定插入哪个。
两个中位数取平均值。