leetcodeノート:Find Median from Data Stream

一.タイトルの説明
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples: [2,3,4] , the median is 3 [2,3] , the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.

double findMedian() - Return the median of all elements so far.

For example:

add(1)
add(2)
findMedian() -> 1.5
add(3) 
findMedian() -> 2

二.テーマ分析
一連の入力データストリームの中で中位数を探すという意味です.中位数とは、整列整数リストの中間値を指します.リストの長さが偶数の場合、中間値はありません.ここで、桁数は2つの中間値の平均値です.
例:[2,3,4]、中位数3[2,3]、中位数(2 + 3) / 2 = 2.5次の2つの操作をサポートするデータ構造を設計します.
void addNum(int num)/データからデータ構造に整数double findMedian()/現在までのすべての要素の中位数を返す
この問題の古典的なやり方は、最大スタックと最小スタックを維持することです.最大スタックはこれまでより小さい半数であり、最小スタックはこれまでより大きい半数であり、中位数はスタックトップまたは2つのスタックトップに対応する2つの数の平均値である可能性がある.
2つのスタックを維持するテクニックは、スタックの先端の数と新しく挿入された数の大きさの関係を判断することであり、また、2つのスタックがすべての数を平分しているため、両者の大きさの関係も考慮する必要がある.ここでは、2つのスタックの大きさの差は1を超えないことを規定しています.スタックトップ数と新しい数の大きさの関係を判断するには、次の3つのケースがあります.

最小スタックトップが新たに挿入された数より小さい場合、新たに挿入された数がすべての数の前半にあることを示す.

最大スタックトップが新しく挿入された数より大きい場合、新しく挿入された数がすべての数の下半分にあることを示します.

最小スタックトップが新規挿入数より大きい場合、最大スタックトップが新規挿入数より小さい場合、新規挿入数が最小スタックトップまたは最大スタックトップ、すなわち中間の位置にあることを示す.

2つのスタックのサイズ関係を判断し、新しく挿入した数が前の2つの場合にターゲットスタックの挿入を開始すると、2つの操作があります.

ターゲットスタックが他のスタックより大きくない場合、新しい数をターゲットスタックに挿入します.

ターゲットスタックが別のスタックより大きい場合は、ターゲットスタックのスタックトップを別のスタックに移動してから、新しい数をターゲットスタックに挿入します.

新しく挿入された数が3番目の場合、すなわち中間位置にある場合は、大きさの小さいスタックに挿入すればよい.このように、新しく1つの数を加えるたびに、2つのスタックが同じ大きさであれば、中位数は2つのスタックの平均値であり、そうでなければ大きなスタックのスタックは中位数である.
2つのスタックを構築するために使用されるコードは比較的長いが、優先キューを使用して実現するのは簡単である.
priority_Queue:優先キューは、重み値の概念を持つ一方向キューです.このキューでは、すべての要素が優先順位で並べられています.優先キューには2種類あり、1つは最大優先キューである.1つは最小優先キューである.キューから取得される最初の要素は、優先度が最も大きく、優先度が最も小さい要素です.
実際に使用する場合、ヘッダファイル:"queue.h","functional.h"ここで"functional.h」は優先度を定義する.(優先順位を自分で定義するには加算しない)優先キューの使用については、次の参照を参照してください.
http://www.cnblogs.com/summerRQ/articles/2470130.html http://blog.csdn.net/zhang20072844/article/details/10286997
三.サンプルコード

class MedianFinder 
{
private: 
    priority_queue<int,std::vector<int>, std::greater<int>> q1; //     ，     
    priority_queue<int> q2; //     ，     

public:

    void addNum(int num) 
    { 
        if(q2.empty())
        {
            q2.push(num);
            return;
        }
        if(num <= q2.top())
        {
            if(q2.size() <= q1.size()) q2.push(num);
            else
            {
                q1.push(q2.top());
                q2.pop();
                q2.push(num);
            }
        } 
        else
        {
            if(q2.size() <= q1.size())
            {
                if(num <= q1.top()) q2.push(num);
                else
                {
                    q2.push(q1.top());
                    q1.pop();
                    q1.push(num);
                }
            }
            else
            {
                q1.push(num);
            }
        }
    }

    double findMedian() 
    {
        if(q1.size() == q2.size()) return (q1.top() + q2.top()) / 2.0;
        return double(q2.top());
    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();

四.小結
優先行列をもう一度真剣に学んで、大きな利益を得た.