做兼职的网站,app制作收费价目表,游戏开发需要的软件,承德网络推广优先队列
思路#xff1a; 中位数是排序中间的数值#xff1a;S1.M.S2可以使用两个优先队列来存放两边的数值#xff0c;总是使得左侧的堆顶是最大的#xff0c;右侧的堆顶是最小的#xff0c;即使用大顶堆存放 S1#xff0c;使用小顶堆存放S2#xff0c;使得两个队列的…优先队列
思路 中位数是排序中间的数值S1.M.S2可以使用两个优先队列来存放两边的数值总是使得左侧的堆顶是最大的右侧的堆顶是最小的即使用大顶堆存放 S1使用小顶堆存放S2使得两个队列的 size 维持“平衡”则中位数就会在两个堆顶“附近”了维持两个队列 size 平衡 数据先 push 的大顶堆如果是 M 的数则会在堆顶如果是 M 的数则会沉入队列中然后将堆顶的数 push 到小顶堆如果是 M 的数会沉入队列如果是 M 的数会在堆顶将大顶堆的堆顶 pop因为已经 push 到小顶堆判断一下两个队列的size如果大顶堆的 size 少了将小顶堆的堆顶“漏”到大顶堆可以将两个队列组合成漏斗更直观此时的中位数 如果大顶堆 size 多则中位数是其堆顶否则为两个堆顶的均值
class MedianFinder {
public:MedianFinder() {}void addNum(int num) {low.push(num);high.push(low.top());low.pop();if (low.size() high.size()) {low.push(high.top());high.pop();}}double findMedian() {if (low.size() high.size()) {return low.top();}return (low.top() high.top()) / 2.0;}private:std::priority_queueint, std::vectorint, std::lessint low;std::priority_queueint, std::vectorint, std::greaterint high;
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj new MedianFinder();* obj-addNum(num);* double param_2 obj-findMedian();*/
