数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中查找整数数组中位数的程序
假设我们必须实现一个名为 MedianClass 的类，其中包含以下方法：
add(value)：将值添加到数据结构中。
median()：查找当前数据结构中所有数字的中位数。
因此，如果我们添加 5、3、8 并查找中位数，则输出将为 5.0，然后如果我们添加 9 并查找中位数，则输出将为 6.5。
为了解决这个问题，我们将遵循以下步骤：
定义优先队列 left 和 right
定义 addNum 方法，它将数字作为输入：
如果 left 为空或 num < left 的顶部元素，则：
将 num 插入到 left 中
否则
将 num 插入到 right 中
如果 left 的大小 < right 的大小，则：
temp := right 的顶部元素
从 right 中删除项目
将 temp 插入到 left 中
如果 left 的大小 - right 的大小 > 1，则：
temp := left 的顶部元素
从 left 中删除项目
将 temp 插入到 right 中
定义 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
更新于： 2020-12-26
219 次查看
广告