C++で整数配列の中央値を見つけるプログラム

• データ構造に値を追加するadd（value）。

• median（）は、データ構造に現在存在するすべての数値の中央値を検索します。

したがって、5、3、8を追加して中央値を見つけると、出力は5.0になり、9を追加して中央値を見つけると、出力は6.5になります。

これを解決するには、次の手順に従います-

• 優先キューを左右に定義する

• addNumメソッドを定義します。これは数値を入力として受け取ります-

• leftが空の場合、またはnum

  • numを左に挿入

• それ以外の場合

  • 右にnumを挿入

• 左のサイズ<右のサイズの場合

  • temp：=右の一番上の要素

  • 右からアイテムを削除

  • 左に温度を挿入

• 左のサイズ-右のサイズ>1の場合、

  • temp：=左の一番上の要素

  • 左からアイテムを削除

  • 温度を右に挿入

• findMedian（）メソッドを定義します。これは次のように機能します-

左のサイズ>右のサイズの場合は左上を返し、それ以外の場合は（左上+右上）/ 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