在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