高质量的高密网站建设,长沙哪里有专业做网站,电脑设计图制作软件app,一个网站做两个优化可以做吗LCR 160. 数据流中的中位数 - 力扣#xff08;LeetCode#xff09;
总结#xff1a;这题自己最开始的想法是直接使用vector容器#xff0c;每次取中位数的时候就进行一次排序#xff0c;超时。题解很巧妙的利用大根堆和小根堆来解决问题#xff0c;大根堆和小根堆各存一…LCR 160. 数据流中的中位数 - 力扣LeetCode
总结这题自己最开始的想法是直接使用vector容器每次取中位数的时候就进行一次排序超时。题解很巧妙的利用大根堆和小根堆来解决问题大根堆和小根堆各存一半的数其中需要注意的是小根堆里面存的是较大的数然后堆顶就是这些数里面最小的数大根堆里面存的是较小的数堆顶就是这些数里面最大的数。这样就可以整体形成一个排好序的序列。
代码
class MedianFinder {
public:/** initialize your data structure here. */priority_queueint,vectorint,greaterint A;priority_queueint,vectorint,lessint 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;}};
