题目描述：
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
数据范围：数据流中数个数满足1≤n≤1000 ，大小满足1≤val≤1000
进阶： 空间复杂度O(n) ， 时间复杂度O(nlogn)
示例：
输入：
[5,2,3,4,1,6,7,0,8]
返回值：
"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
说明：
数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...
解题思路：
本题是排序题目。三种解题思路。
1）快速排序
按顺序插入，获取中位数时进行快速排序，然后根据奇偶尺寸分情况输出结果。
时间复杂度O(nlogn)，空间复杂度O(n)。
2）插入排序
基于插入排序思想，插入时先分析数据应该插入的位置，这样就能保持数据集合的有序性，获取中位数直接根据奇偶尺寸分情况输出结果。
插入操作的时间复杂度为二分查找和移动数据的最大值，O(n)，又因为进行了n次插入，所以时间复杂度最坏为O(n2)，最好为O(n)，空间复杂度O(n)。
3）堆排序
用两个优先序列（大小顶堆）将整个数据分为大小两部分，维持动态平衡进行插入，获取中位数直接根据奇偶尺寸分情况，从大小顶堆的根获取数据计算即可。
时间复杂度O(nlogn)，空间复杂度O(n)。
测试代码：
1）快速排序
#include <algorithm> class Solution { public: vector<int> v; // 插入 void Insert(int num) { v.emplace_back(num); } // 获取中位数 double GetMedian() { int size = int(v.size()); sort(v.begin(), v.end()); // 奇偶分情况讨论 // 右移1位等于除以2 if(size & 1){ return double(v[size >> 1]); } else{ return double(v[size >> 1] + v[(size - 1) >> 1]) / 2; } } };
2）插入排序
#include <algorithm> class Solution { public: vector<int> v; // 插入 void Insert(int num) { // 查找合适插入的位置 auto idx = lower_bound(v.begin(), v.end(), num); v.insert(idx, num); } // 获取中位数 double GetMedian() { int size = int(v.size()); // 奇偶分情况讨论 // 右移1位等于除以2 if(size & 1){ return double(v[size >> 1]); } else{ return double(v[size >> 1] + v[(size - 1) >> 1]) / 2; } } };
3）堆排序
class Solution { public: priority_queue<int> minp; // 大顶堆 priority_queue<int, vector<int>, greater<int>> maxp; // 小顶堆 // 插入 void Insert(int num) { // 大顶堆中存放数据 minp.push(num); // 取大顶堆中最大的值放入小顶堆中 maxp.push(minp.top()); minp.pop(); // 平衡两堆数据数量 if (minp.size() < maxp.size()){ minp.push(maxp.top()); maxp.pop(); } } // 获取中位数 double GetMedian() { return minp.size() > maxp.size() ? static_cast<double>(minp.top()) : static_cast<double>(minp.top() + maxp.top()) / 2; } };
