【剑指 offer】 41. 数据流中的中位数-爱代码爱编程

此题用大根堆和小根堆来找到中位数，解法比较巧妙，另外学习了大根堆的使用方式，赚到了。(๑•̀ㅂ•́)و✧

具体过程比较复杂，请参考题解：力扣https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/solution/mian-shi-ti-41-shu-ju-liu-zhong-de-zhong-wei-shu-y/

代码如下：

from heapq import *
class MedianFinder:
    def __init__(self):
        """
        initialize your data structure here.
        """
        # 初始化小顶堆A和大顶堆B(大顶堆的实现方式是小顶堆push和pop的时候都取反就ok了)
        self.A,self.B = [],[]

    def addNum(self, num: int) -> None:
        # 如果长度不相等，把当前num添加到大顶堆B中使长度相等，否则将num添加到小顶堆A中
        # 这里不能直接将num添加到B中的原因是当前的num可能是较大的那一堆，应该把小顶堆中的堆顶元素给B
        if len(self.A)!=len(self.B):
            # heappush(self.A,num)
            # heappush(self.B,-heappop(self.A))
            heappush(self.B,-heappushpop(self.A,num))

        else:
            # heappush(self.B,-num)
            # heappush(self.A,-heappop(self.B))
            heappush(self.A,-heappushpop(self.B,-num))

    def findMedian(self) -> float:
        return self.A[0] if len(self.A)!=len(self.B) else (self.A[0]-self.B[0])/2



# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()