找出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