题目：

  1. 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
  3. 例如，
  5. [2,3,4] 的中位数是 3
  7. [2,3] 的中位数是 (2 + 3) / 2 = 2.5
  9. 设计一个支持以下两种操作的数据结构：
  11. void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  12. double findMedian() - 返回目前所有元素的中位数。
  13. 示例 1：
  15. 输入：
  16. ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
  17. [[],[1],[2],[],[3],[]]
  18. 输出：[null,null,null,1.50000,null,2.00000]
  19. 示例 2：
  21. 输入：
  22. ["MedianFinder","addNum","findMedian","addNum","findMedian"]
  23. [[],[2],[],[3],[]]
  24. 输出：[null,null,2.00000,null,2.50000]
  27. 限制：
  29. 最多会对 addNum、findMedian 进行 50000 次调用。

分析

这一题其实要我们去写一个数据结构中的函数
但是既然是hard的话那肯定对时间复杂度会有严格的要求

其实中位数的计算本身不难，给我一个数组，我先对其排序，然后取中间位置的数进行计算即可

所以为了达到效率高的要求
我们需要在addNum() 时就维护好“数组”中元素的大小关系，这样可以方便我们快速的去计算中位数；

但是在addNum()时会有一个问题，那就是用什么数据结构；vector？用vector 的好处就是可以快速用下标来进行访问，但是也有缺点，那就是我在插入这个数字的时候，我通过比如二分法来找到数字的插入的位置之后进行插入操作时，会遇到效率较低的情况，只能说把后面的数字都后移一位？O(N)

有没有其他数据结构可以来做？
大顶堆？

因为中位数我们其实只需要知道最中间的露头的数字
所以我们可以用一个 大顶堆+一个小顶堆 维护顺序
我们始终保持 小顶堆数量和大顶堆数量相同（偶数时） 或 小顶堆数量和大顶堆中数的个数 相差为1（奇数）即可
O(logN)

代码：

  1. class MedianFinder {
  2. public:
  3.     // 最大堆，存储左边一半的数据，堆顶为最大值
  4.     priority_queue<int, vector<int>, less<int>> maxHeap;
  5.     // 最小堆， 存储右边一半的数据，堆顶为最小值
  6.     priority_queue<int, vector<int>, greater<int>> minHeap;
  7.     /** initialize your data structure here. */
  8.     MedianFinder() {
  9.     }
  11.     // 维持堆数据平衡，并保证左边堆的最大值小于或等于右边堆的最小值
  12.     void addNum(int num) {
  13.         /*
  14.          * 当两堆的数据个数相等时候，左边堆添加元素。
  15.          * 采用的方法不是直接将数据插入左边堆，而是将数据先插入右边堆，算法调整后
  16.          * 将堆顶的数据插入到左边堆，这样保证左边堆插入的元素始终是右边堆的最小值。
  17.          * 同理左边数据多，往右边堆添加数据的时候，先将数据放入左边堆，选出最大值放到右边堆中。
  18.          */
  19.         if (maxHeap.size() == minHeap.size()) {
  20.             minHeap.push(num);
  21.             int top = minHeap.top();
  22.             minHeap.pop();
  23.             maxHeap.push(top);
  24.         } else {
  25.             maxHeap.push(num);
  26.             int top = maxHeap.top();
  27.             maxHeap.pop();
  28.             minHeap.push(top);
  29.         }
  30.     }
  32.     double findMedian() {
  33.         if (maxHeap.size() == minHeap.size()) {
  34.             return (maxHeap.top()+minHeap.top())*1.0/2;
  35.         } else {
  36.             return maxHeap.top()*1.0;
  37.         }
  38.     }
  39. };