算法训练|数据流中的中位数
LCR 160. 数据流中的中位数 - 力扣（LeetCode）
总结：这题自己最开始的想法是直接使用vector容器，每次取中位数的时候就进行一次排序，超时。题解很巧妙的利用大根堆和小根堆来解决问题，大根堆和小根堆各存一半的数，其中需要注意的是，小根堆里面存的是较大的数，然后堆顶就是这些数里面最小的数，大根堆里面存的是较小的数，堆顶就是这些数里面最大的数。这样就可以整体形成一个排好序的序列。
代码：
class MedianFinder {
public:
/** initialize your data structure here. */
priority_queue<int,vector<int>,greater<int>> A;
priority_queue<int,vector<int>,less<int>> B;
MedianFinder() {
}
void addNum(int num) {
if(A.size() != B.size())
{
A.push(num);
B.push(A.top());
A.pop();
}
else
{
B.push(num);
A.push(B.top());
B.pop();
}
}
double findMedian() {
return A.size() != B.size() ? A.top() : (A.top() + B.top()) / 2.0;
}
};