在C ++中从数据流中查找中位数
假设我们有一个数据流，在该数据流中可能会有一些数据元素加入并加入，我们必须建立一个系统，这将有助于从数据中查找中值。我们知道中位数是排序列表的中间数据，如果列表长度是奇数，则可以直接获取中位数，否则取中间两个元素，然后求出平均值。因此将有两种方法，addNum()和findMedian()，这两种方法将用于将数字加到流中，并找到所有加法数字的中位数
为了解决这个问题，我们将遵循以下步骤-
左右定义优先级队列
定义addNum方法，它将数字作为输入-
如果left为空或num<left的顶部元素，则，
在左侧插入num
除此以外
在右边插入num
如果left的大小<right的大小，那么，
temp：=右侧的顶部元素
从右边删除项目
将温度插入左侧
如果left的大小–right的大小>1，则，
temp：=左侧的顶部元素
从左侧删除项目
将温度插入右边
定义findMedian()方法，其作用如下-
如果left的大小>right的大小，则返回left的顶部，否则返回（left的顶部+right的顶部）/2
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
typedef double lli;
class MedianFinder {
priority_queue <int> left;
priority_queue <int, vector <int>, greater<int>> right;
public:
void addNum(int num) {
if(left.empty() || num<left.top()){
left.push(num);
}else right.push(num);
if(left.size()<right.size()){
lli temp = right.top();
right.pop();
left.push(temp);
}
if(left.size()-right.size()>1){
lli temp = left.top();
left.pop();
right.push(temp);
}
}
double findMedian() {
return
left.size()>right.size()?left.top():(left.top()+right.top())*0.5;
}
};
main(){
MedianFinder ob;
ob.addNum(10);
ob.addNum(15);
cout << ob.findMedian() << endl;
ob.addNum(25);
ob.addNum(30);
cout << ob.findMedian() << endl;
ob.addNum(40);
cout << ob.findMedian();
}输入值
addNum(10); addNum(15); findMedian(); addNum(25); addNum(30); findMedian(); addNum(40); findMedian();
输出结果
12.5 20 25