找出C ++中整数数组中位数的程序
假设我们必须实现一个名为MedianClass的类，其中包含以下方法-
add(value)这会为数据结构添加一个值。
median()查找数据结构中当前存在的所有数字的中位数。
因此，如果我们加上5、3、8并找到中位数，则输出将为5.0，然后如果我们加上9并找到中位数，则输出将为6.5。
为了解决这个问题，我们将遵循以下步骤-
左右定义优先级队列
定义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 MedianClass {
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(){
MedianClass ob;
ob.addNum(5);
ob.addNum(3);
ob.addNum(8);
cout << ob.findMedian() << " ";
ob.addNum(9);
cout << ob.findMedian() << endl;
}输入值
ob.addNum(5); ob.addNum(3); ob.addNum(8); cout << ob.findMedian() << endl; ob.addNum(9); cout << ob.findMedian() << endl;输出结果
5.0 6.5