原题地址（困难）

方法1—优先队列/堆

思路

这道题没啥好说的，直接上优先队列。
开始我想的是用一个列表，然后不断插入，维持列表有序，所以时间复杂度在O(n)，结果会超时。
这道题就是为优先队列量身定制，时间复杂度为O(logN)。
也是通过这道题学习了c++和Python优先队列的使用

代码

c++

  1. class MedianFinder {
  2.     priority_queue<int> lo;                              // max heap
  3.     priority_queue<int, vector<int>, greater<int>> hi;   // min heap
  5. public:
  6.     // Adds a number into the data structure.
  7.     void addNum(int num)
  8.     {
  9.         lo.push(num);                                    // Add to max heap
  11.         hi.push(lo.top());                               // balancing step
  12.         lo.pop();
  14.         if (lo.size() < hi.size()) {                     // maintain size property
  15.             lo.push(hi.top());
  16.             hi.pop();
  17.         }
  18.     }
  20.     // Returns the median of current data stream
  21.     double findMedian()
  22.     {
  23.         return lo.size() > hi.size() ? (double) lo.top() : (lo.top() + hi.top()) * 0.5;
  24.     }
  25. };

Python

要注意Python只有小顶堆，没有大顶堆，所以把元素取负值，才能实现大顶堆效果。

  1. class MedianFinder:
  3.     def __init__(self):
  4.         """
  5.         initialize your data structure here.
  6.         """
  7.         self.count = 0
  8.         self.maxHeap = []
  9.         self.minHeap = []
  11.     def addNum(self, num: int) -> None:
  12.         self.count += 1
  13.         # python只有小顶堆，所以把num取负传入，才可实现大顶堆效果
  14.         heapq.heappush(self.maxHeap, -num)
  15.         maxHeap_top = -heapq.heappop(self.maxHeap) # 取大顶堆top元素
  16.         heapq.heappush(self.minHeap, maxHeap_top)  # 传入小顶堆
  17.         if self.count & 1:  # 如果元素总数为奇数，则让大顶堆多一个元素
  18.             heapq.heappush(self.maxHeap, -heapq.heappop(self.minHeap))
  20.     def findMedian(self) -> float:
  21.         if self.count & 1:
  22.             return -self.maxHeap[0]
  23.         else:
  24.             return (-self.maxHeap[0] + self.minHeap[0]) * 0.5

时空复杂度

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