【Leetcode Daily】295数据流的中位数

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是在给数组增添数字的过程中，可能需要随时输出当前的中位数。

思路分享

• 构建大小堆，也就是一个大顶堆和一个小顶堆，前者相当于当前数字的左侧，后者相当于右侧，这样就能随时得到左边最大和右边最小的数值，也就方便计算中位数了。

  https://leetcode.cn/problems/find-median-from-data-stream/solutions/3015873/ru-he-zi-ran-yin-ru-da-xiao-dui-jian-ji-4v22k/

• 具体而言，需要保证两点，第一是优先把数字放左侧，随后如果左侧的数字更多，再放右边；第二保证左侧的所有数字都小于右侧，所以如果要加到左侧的数字，可以先加到右侧，再从右侧获取最小的数字加到左侧。

代码解答（强烈建议自行解答后再看）

• 参考题解

class MedianFinder:

    def __init__(self):
        self.left = []
        self.right = []

    def addNum(self, num: int) -> None:
        if len(self.left) == len(self.right):
            heappush(self.left, -heappushpop(self.right, num))
        else:
            heappush(self.right, -heappushpop(self.left, -num))

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


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