中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类，包括以下方法：
MedianFinder(): 初始化 MedianFinder 对象addNum(int num): 将数据流中的整数 num 添加到数据结构中findMedian(): 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受示例 1：
输入： ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出： [null, null, null, 1.5, null, 2.0] 解释： MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // 返回 2.0提示：
-105 <= num <= 105 在调用 findMedian 之前，数据结构中至少有一个元素 最多 5 * 10^4 次调用 addNum 和 findMedian
思考
- 这题要求的数据结构只有插入没有弹出
- 从这道题要求的时间看，插入和寻找中位数的时间复杂度都应该选择比较低的
- 如果要在插入元素后快速得到中位数，那么这种数据结构应该是有序的，否则遍历得到中位数的时间复杂度将是O(n)
- 对有序数据结构，插入后仍然保持有序，可以想到使用二分插入，那么二分寻找插入位置的时间复杂度就是O(logn)
- 如果使用数组来实现二分插入，虽然二分寻找插入位置的时间复杂度为O(logn)，但是由于插入后数据需要后挪，移动的时间复杂度是O(n)
- 堆的插入时间就只有O(logn)，且能以常数时间找到最小或者最大的值（小顶堆和大顶堆），但是这道题是要求查找中位数，而堆并不能实现中位数的常数寻找
- 但是中位数的特性是，在一个升序序列上，中位数左边的数字都比它小，右边的数字都比他大。那么可以将比中位数小的元素放入大顶堆，比中位数大的元素放入小顶堆，这样就可以将中位数暴露在堆顶，插入元素时，选择放入其中一个堆，此时堆顶（中位数）可能会更新，将更新后的中位数也执行插入即可
解法：大顶堆+小顶堆
- 设大顶堆为A，小顶堆为B
- 假设大顶堆A 保存较小的一半以及中位数，而小顶堆B 保存较大的一半
- 那么当元素总个数为奇数时，大顶堆A 的元素个数就比小顶堆多 1，且中位数为大顶堆A 的顶
- 当元素个数为偶数时，两个堆的元素数量一致，中位数为两个堆堆顶的平均值
- 搞定了中位数的查找，接下来就解决插入问题
- 当当前元素总数为偶数时，两个堆的元素数量都一致，那么如果此时要新增一个元素，按照上面说的：假设大顶堆A 保存较小的一半以及中位数，则应该把这个元素插入大顶堆A中，这样元素总数为奇数后中位数就是大顶堆A 的堆顶
- 但是新增的元素可能并不属于较小的那一半，直接插入大顶堆A 会破坏 A 的结构，所以需要将其先放入小顶堆B 中清洗一下。如果新增的元素确实属于较小的那一半，那么在放入小顶堆后会被暴露在堆顶，此时将 B堆顶插入大顶堆A 即可；如果新增的元素属于较大的那一半，那么放入小顶堆后并不会改变小顶堆的堆顶元素，但是为了保持小顶堆B 的元素个数（因为本来是要向大顶堆A 中插入元素的），则需要把大顶堆B 的堆顶元素插入小顶堆A 中
- 以此类推，当当前元素总数为奇数时，小顶堆A 元素比大顶堆元素多一个，新增元素就要插入大顶堆B 中，但是也需要放入小顶堆A 中进行数据清洗后，再找出合适的元素插入大顶堆B
class MedianFinder {
//设大顶堆的元素比小顶堆多0或1个，也就是有奇数个元素时大顶堆堆顶即为中位数
priority_queue<int, vector<int>, greater<int>> minHeap;//小顶堆
priority_queue<int> maxHeap;//大顶堆
int n=0;//总元素个数
public:
MedianFinder() {
}
void addNum(int num) {
if(n%2){//元素个数为奇数，最终要在小顶堆中新增元素
maxHeap.push(num);//先放入大顶堆中清洗数据
minHeap.push(maxHeap.top());//再把大顶堆堆顶存入小顶堆中
maxHeap.pop();
}
else{//元素个数为偶数
minHeap.push(num);
maxHeap.push(minHeap.top());
minHeap.pop();
}
++n;
}
double findMedian() {
if(n%2) return maxHeap.top();
else return (maxHeap.top()+minHeap.top())/2.0;
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
