数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++数据流中查找中位数
假设我们有一个数据流，在这个数据流中，一些数据元素可能会加入，我们需要创建一个系统来帮助查找数据的中位数。众所周知，中位数是有序列表中间的数据，如果列表长度为奇数，可以直接得到中位数；否则，取中间两个元素，然后求平均值。因此，将有两种方法：addNum() 和 findMedian()，这两种方法将用于将数字添加到流中，并查找所有已添加数字的中位数。
为了解决这个问题，我们将遵循以下步骤：
定义优先级队列 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 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
更新于：2020年5月27日
373 次查看
广告