假设我们有一个数据流,在该数据流中可能会有一些数据元素加入并加入,我们必须建立一个系统,这将有助于从数据中查找中值。我们知道中位数是排序列表的中间数据,如果列表长度是奇数,则可以直接获取中位数,否则取中间两个元素,然后求出平均值。因此将有两种方法,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