1. 题目来源
链接：295. 数据流的中位数
相关博文：
2. 题目解析
十分经典的问题了。算法常用，剑指 offer 中也会出现，这个数据结构设计的十分巧妙！
思路：
- 中位数，实际上就是将数组分成有序的两段，L、R。当 L == R 时就是两端相邻点的平均值，当 L = R +1 时，就是 L 中多出来的那个数。
- 如果需要动态维护的话，一般思路：
- 将 L 设置成大顶堆，L 中实际上存的是数组中较小的一部分数，而堆顶是这较小数的最大值，方便向 R 去移动。
- 将 R 设置成小顶堆，R 中实际上存的是数组中较大的一部分数，而堆顶是这较大数的最小值，方便向 L 去移动。
- 设定：L.size() >= R.size() + 1，我们设置 L 的元素个数至多比 R 多一个。在这个设置下，中位数就可以从两个堆顶元素求得了。
- 当 num 进入时，如果：
- L.size() == R.size()，加入后，应当变成 L.size() = R.size() + 1，那么我们希望从将 R 中最小的一个加入到 L 中，所以 num 先进入 R，然后再将 R 堆顶元素加入 L，最后将 R 堆顶元素弹出。这样子做，不需要考虑 num 与 L、R 堆顶元素的大小关系。
- L.size() != R.size()，说明 L.size() = R.size() +1，加入后，应当变成 L.size() == R.size() 才对，那么我们希望将 L 中最大的一个加入到 R 中去，所以 num 先进入 L 进行比较，然后再将 L 的堆顶元素加入 R，最后将 L 堆顶元素弹出，这样子做，也不需要考虑 num 与 L、R 堆顶元素的大小关系。
- 获取中位数时，两个情况：
- L.size() == R.size() 那么取 L、R 堆顶元素的平均值即可。
- L.size() != R.size() 基于我们之前的设定，现在应该是 L.size() == R.size() + 1，那么直接返回 L 的堆顶元素即为中位数。
这个思路很是巧妙，可以自行画图理解下~
学习一下这个代码实现，避免情况判断。但是在效率上可能较低，如果明确了 num 和 堆顶的关系，可能我们直接进行 push 一次就行了，但实际在这里一直都是 push 两次 pop 一次。
eg：
- 其实这里设定 L.size() >= R.size() +1 是很灵活的一个人为设定，同理我们设置 R.size() >= L.size()+1 也行，主要是为了维护左右两端的一个平衡而已。可以类比下 AVL 树。
- 时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
- 空间复杂度： O ( n ) O(n) O(n)
class MedianFinder {
public:
priority_queue<int, vector<int>, less<int>> L;
priority_queue<int, vector<int>, greater<int>> R;
MedianFinder() {
}
void addNum(int num) {
if (L.size() != R.size()) {
L.push(num);
R.push(L.top());
L.pop();
} else {
R.push(num);
L.push(R.top());
R.pop();
}
}
double findMedian() {
return L.size() == R.size() ? (L.top() + R.top()) / 2.0 : L.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
