算法训练|数据流中的中位数

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;}};