LeetCode 295. Find Median from Data Stream (hard)

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

  1. 例如，
  3. [2,3,4] 的中位数是 3
  5. [2,3] 的中位数是 (2 + 3) / 2 = 2.5
  7. 设计一个支持以下两种操作的数据结构：
  9. void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  10. double findMedian() - 返回目前所有元素的中位数。
  11. 示例：
  13. addNum(1)
  14. addNum(2)
  15. findMedian() -> 1.5
  16. addNum(3)
  17. findMedian() -> 2

进阶:

  • 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
  • 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

返回结果

当数字总个数为奇数的时候，返回堆元素更多的那个堆的堆顶为中位数
当数字总个数为偶数的时候，返回两个堆堆顶的平均数为中位数

代码

  1. class MedianFinder {
  2. public:
  3.     priority_queue<int, vector<int>, less<int>> larger;
  4.     priority_queue<int, vector<int>, greater<int>> smaller;
  6.     /** initialize your data structure here. */
  7.     MedianFinder() {
  9.     }
  11.     void addNum(int num) {
  12.         if(larger.empty() || num <= larger.top()){
  13.             larger.push(num);
  14.             if(larger.size() == smaller.size()+2){
  15.                 smaller.push(larger.top());
  16.                 larger.pop();
  17.             }
  18.         }
  19.         else{
  20.             smaller.push(num);
  21.             if(smaller.size() == larger.size()+2){
  22.                 larger.push(smaller.top());
  23.                 smaller.pop();
  24.             }
  25.         }
  26.     }
  28.     double findMedian() {
  29.         int total = larger.size()+smaller.size();
  30.         if(total & 1){
  31.             if(larger.size()>smaller.size()){
  32.                 return (double) larger.top();
  33.             }else{
  34.                 return (double) smaller.top();
  35.             }
  36.         }
  37.         return (double) (larger.top()+smaller.top()) /2;
  38.     }
  39. };