剑指offer：数据流中的中位数

题目描述：

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

思路分析：

思路一：最朴素的想法，用一个vector来存输入的数据流。在取中位数的函数中，每次对数据流进行一次排序，对于奇数长度的数据，直接取中间值，对于偶数长度的数据，取中间两个数的平均值。很显然，这个方法是不能令人满意的。对于每一次新加入一个数据后，都需要重新进行一次排序，那么对于n个输入的n次查询，时间复杂度就会达到O(n^2logn），是不可接受的。

思路二：实际上，比较多的解法是考虑用堆来实现这个算法，分别维护一个最大堆和一个最小堆。保持两个堆中的数据个数相等，堆内部不需要排序，最大堆中的数始终小于最小堆中的数。同时约定，当总数据个数为偶数时，再有一个数加入，都往最小堆加，加入后，再取出最小堆中的第一个元素即最小值，加入到最大堆中。当为奇数时，先加入最大堆，再将最大堆的首元素即最大值取出加入最小堆。这样，当总数为奇数时，中位数为最大堆中的首元素，当为偶数时，分别取两个堆的首元素再求平均。

代码：

思路一：

 1 class Solution {
 2 public:
 3     vector<int> DataStream;
 4     void Insert(int num)
 5     {
 6         DataStream.push_back(num);
 7     }
 8 
 9     double GetMedian()
10     { 
11         sort(DataStream.begin(), DataStream.end());
12         int len = DataStream.size();
13         double res;
14         if(len%2==1)
15             res = DataStream[len/2];
16         else
17             res = (DataStream[len/2-1]+DataStream[len/2])/2.0;
18         return res;
19     }
20 
21 };

思路二：

 1 class Solution {
 2 public:
 3     vector<int> min;
 4     vector<int> max;
 5     int count = 0;
 6     void Insert(int num)
 7     {
 8         if(count%2 == 0)
 9         {
10             min.push_back(num);
11             push_heap(min.begin(), min.end(), greater<int>());
12             max.push_back(min[0]);
13             push_heap(max.begin(), max.end(), less<int>());
14             pop_heap(min.begin(), min.end(), greater<int>());
15             min.pop_back();
16         }
17         else
18         {
19             max.push_back(num);
20             push_heap(max.begin(), max.end(), less<int>());
21             min.push_back(max[0]);
22             push_heap(min.begin(), min.end(), greater<int>());
23             pop_heap(max.begin(), max.end(), less<int>());
24             max.pop_back();
25         }
26         count++;
27     }
28 
29     double GetMedian()
30     { 
31         if(count%2==1)
32             return double(max[0]);
33         else
34             return double((min[0]+max[0])/2.0);
35     }
36 
37 };