题目

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

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


示例：

  1. addNum(1)
  2. addNum(2)
  3. findMedian() -> 1.5
  4. addNum(3) 
  5. findMedian() -> 2

注：典型的 TP99 问题

方案一（两个堆）**

  1. class MedianFinder:
  3.     def __init__(self):
  4.         """
  5.         initialize your data structure here.
  7.         1. lo 为大顶堆
  8.         2. hi 为小顶堆
  10.         每个堆各保持一半的元素，如果元素总数为奇数个，则放入大顶堆
  11.         """
  12.         self.hi = []
  13.         self.lo = []
  15.     def addNum(self, num: int) -> None:
  16.         # 注意调整堆的平衡
  17.         heapq.heappush(self.lo, num)
  18.         heapq.heappush(self.hi, -heapq.heappop(self.lo))
  20.         if len(self.lo) < len(self.hi):
  21.             heapq.heappush(self.lo, -heapq.heappop(self.hi))
  23.     def findMedian(self) -> float:
  24.         if (len(self.hi) + len(self.lo)) % 2 == 1:
  25.             return self.lo[0]
  26.         else:
  27.             return (self.lo[0] - self.hi[0]) / 2

原文

https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/291/design/1303/
https://leetcode-cn.com/problems/find-median-from-data-stream/solution/shu-ju-liu-de-zhong-wei-shu-by-leetcode/