295_数据流的中位数

类型：堆

• 295. 数据流的中位数 ❤️ ⭐

  https://leetcode-cn.com/problems/find-median-from-data-stream/

  ❓ 实现一个支持中位数获取的数据流结构。包含如下方法：

  • void addNum(int num)

    添加数据 num 到数据流中。

  • double findMedian()

    返回当前的中位数。

  💡 堆

  我们维护两个堆，一个是大顶堆，一个是小顶堆，保持这两个堆的大小之差不超过 1.

  class MedianFinder:
  
      def __init__(self):
          """
          initialize your data structure here.
          """
          self.leftHeap = [] # 左堆是大顶堆
          self.rightHeap = [] # 右堆是小顶堆
  
      def addNum(self, num: int) -> None:
          if not self.leftHeap or num < -1 * min(self.leftHeap):
              # 插入到左堆中
              heapq.heappush(self.leftHeap, -1 * num)
          else:
              # 插入到右堆中
              heapq.heappush(self.rightHeap, num)
          # 调整两个堆的大小
          if len(self.leftHeap) - len(self.rightHeap) < 0:
              # 右堆移给左堆
              heapq.heappush(self.leftHeap, -1 * heapq.heappop(self.rightHeap))
          elif len(self.leftHeap) - len(self.rightHeap) > 1:
              # 左堆移给右堆
              heapq.heappush(self.rightHeap, -1 * heapq.heappop(self.leftHeap))
  
      def findMedian(self) -> float:
          if not self.leftHeap and not self.rightHeap:
              return 0
          if len(self.leftHeap) == len(self.rightHeap):
              return (-1 * min(self.leftHeap) + min(self.rightHeap)) / 2
          else:
              return -1 * min(self.leftHeap)

  时间复杂度：O(logN)，空间复杂度：O(N)