C++のデータストリームから中央値を見つける

データストリームがあり、そのストリームにいくつかのデータ要素が来て参加する可能性があるとすると、データから中央値を見つけるのに役立つ1つのシステムを作成する必要があります。中央値は並べ替えられたリストの中央値であることがわかっているので、リストの長さが奇数の場合は中央値を直接取得できます。それ以外の場合は、中央値の2つの要素を取得して、平均を求めます。したがって、addNum（）とfindMedian（）の2つのメソッドがあり、これら2つのメソッドを使用して、ストリームに数値を追加し、追加されたすべての数値の中央値を検索します。

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

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

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

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

  • numを左に挿入

• それ以外の場合

  • 右にnumを挿入

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

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

  • 右からアイテムを削除

  • 左に温度を挿入

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

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

  • 左からアイテムを削除

  • 温度を右に挿入

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

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