剑指Offer 41：数据流中的中位数

Leetcode 295. Find Median from Data Stream

• 首先使用python的堆库heapq，使用的方法如下

• heapq默认为最小堆，可以通过存入相反数转变为最大堆

方法一：构造最大堆+最小堆，其中最小堆和最大堆大小最多差一个，最小堆所有元素大于最大堆元素

class MedianFinder:
    import heapq

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.min_heap, self.max_heap = list(), list()

    def addNum(self, num: int) -> None:
        if (len(self.min_heap) + len(self.max_heap)) % 2 == 0:
            if len(self.min_heap) > 0 and num < -self.max_heap[0]:
                heapq.heappush(self.min_heap, -heappop(self.max_heap))
                heapq.heappush(self.max_heap, -num)
            else:
                heapq.heappush(self.min_heap, num)
        else:
            if num > self.min_heap[0]:
                heapq.heappush(self.max_heap, -heappop(self.min_heap))
                heapq.heappush(self.min_heap, num)
            else:
                heapq.heappush(self.max_heap, -num)

    def findMedian(self) -> float:
        if len(self.min_heap) + len(self.max_heap) == 0:
            return None
        elif (len(self.min_heap) + len(self.max_heap)) % 2:
            return self.min_heap[0]
        else:
            return (self.min_heap[0] - self.max_heap[0]) / 2

Leetcode上的剪短写法

class MedianFinder:
    import heapq

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.data = None, list(), list()
        self.i = 1

    def addNum(self, num: int) -> None:
        heapq.heappush(self.data[self.i], -heapq.heappushpop(self.data[-self.i], num * self.i))
        self.i *= -1

    def findMedian(self) -> float:
        return (-self.data[1][0] + self.i * self.data[-self.i][0]) / 2