自己创建的网站怎么做流量,网站建设 推广全流程,品牌vi包括什么,做兼职一般去哪个网站好
一、思路 我们将所有数据平分成两份#xff0c;前面那一部分用小堆来存#xff0c;后面的部分用大堆来存#xff0c;这样我们就能立刻拿到中间位置的值。 如果是奇数个数字#xff0c;那么我们就将把中间值放在前面的大堆里#xff0c;所以会有两种…
一、思路 我们将所有数据平分成两份前面那一部分用小堆来存后面的部分用大堆来存这样我们就能立刻拿到中间位置的值。 如果是奇数个数字那么我们就将把中间值放在前面的大堆里所以会有两种情况我们将大堆成为left小堆成为right。
当数据量是偶数的时候left.size() right.size()这时候中间值就是left.top()当数据量是奇数的时候这时候的left.size() right.size() 1这时候的中位数就是 (left.size() right.size()) / 2.0
二、如何存储数据
因为左边是大堆右边是小堆这时候会有两个大类的情况 第一种 left.size() right.size() 这时候由于左边的数据都是会比left.top()小右边的数据都会比左边的数据大所以我们可以根据这个条件开进行讨论 假如要插入的数据是num 如果left.empty() || num left.top() 这时候就直接将num插进左边的大堆中如果num left.top()这时候应该要插进右边的小堆但由于我们规定只能两边数据相等或者右边的比左边的数据量多一个所以这时候我们要 1.先把数据插入进right 2.然后拿到right.top(),因为这是right的最小值 3.将right.top() 插进 left.top()中然后再让right.pop() 第二种 left.size() right.size() 如果num left.top() 直接把num插进right中如果num left.top() 这时候由于left的大小比right多1所以我们可以参考第一种情况那样 把数据插进left将left.top() 插入到 right中left.pop() 三、代码
class MedianFinder {
public:priority_queueint left;priority_queueint, vectorint, greaterint right;MedianFinder() {}void addNum(int num) {if(left.size() right.size()){if(left.empty() || left.top() num) {left.push(num);}else if(left.top() num) {right.push(num);int y right.top();right.pop();left.push(y);}}else{if(left.top() num) {left.push(num);right.push(left.top());left.pop();}else {right.push(num);}}}double findMedian() {if(left.size() right.size()) return (left.top() right.top()) / 2.0;else return left.top();}
};
