题目

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

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

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。

示例： addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2

题解

维护两个堆：大顶堆和小顶堆。并且需满足如下条件：

• 小顶堆的所有元素都大于等于大顶堆的所有元素。
• 大顶堆中的元素数量大于等于小顶堆中的元素数量。 大顶堆对应排序后的列表的左半部分；小顶堆对应排序后的列表的右半部分。不仅要维护大顶堆和小顶堆的元素个数之差不超过 1，还要维护大顶堆的堆顶元素要大于等于小顶堆的堆顶元素。想要往大顶堆里添加元素，不能直接添加，而是要先往小顶堆里添加，然后再把小顶堆的堆顶元素加到大顶堆中；向小顶堆中添加元素同理。

当拿来一个数num，做出如下操作：

如果大顶堆中的元素数量等于小顶堆中的元素数量，则先将num插入到小顶堆，再将小顶堆的堆顶元素插入到大顶堆； 否则，先将num插入到大顶堆，再将大顶堆的堆顶元素插入到小顶堆。 python的heapq默认实现小顶堆的操作，要实现大顶堆，需要将元素取负。

class MedianFinder:

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

    def addNum(self, num: int) -> None:
        if len(self.max_heap) == len(self.min_heap):
            heapq.heappush(self.max_heap, - heapq.heappushpop(self.min_heap, num))
        else:
            heapq.heappush(self.min_heap, - heapq.heappushpop(self.max_heap, -num))

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