剑指offer-python：38.数据流中的中位数

剑指offer-python：38.数据流中的中位数

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

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

思路：使用两个堆，最大堆存储较小的数据，最小堆存储较大的数据。添加数字时，先添加到最大堆，然后最大堆返回一个最大的数字给最小堆，最后为了平衡，可能需要最小堆还给最大堆一个最小值，以保证最大堆的长度>=最小堆的长度。由于headpq是最小堆，所以使用取反实现最大堆。添加数字：Time-O(logn)，取出中位数：Time-O(1)。

调用heapq库。

代码：

import heapq as hq

class MedianFinder:
    def __init__(self):
        self.lo , self.hi = [] , []

    def addN(self , num):
        hq.heappush(self.lo , -num)
        hq.heappush(self.hi , -hq.heappop(self.lo))

        print('lo = {} , hi = {}'.format(self.lo , self.hi))

        if len(self.lo) < len(self.hi):
            hq.heappush(self.lo , -hq.heappop(self.hi))

    def findMedian(self ):
        if len(self.lo) == len(self.hi):
            return (-self.lo[0] + self.hi[0]) / 2.0
        else:
            return float(-self.lo[0])