leetcode筆記：Find Median from Data Stream

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,3,4], 中位數是 3

[2,3], 中位數是 (2 + 3) / 2 = 2.5

設計一種數據結構，支持下面兩種操作：

void addNum(int num) // 該函數從數據流向數據結構加入一個整數
double findMedian() // 返回截至目前所有元素的中位數

該題的經典做法是，維護一個最大堆和一個最小堆。最大堆存的是截至目前為止較小的那一半數，最小堆存放的是截至目前為止較大的那一半數，這樣中位數只有可能是堆頂或者兩個堆頂所對應兩個數的平均值。

維護兩個堆的技巧在於判斷堆頂端的數和新插入的數的大小關系，另外，由於兩個堆平分了所有數，因此還需要考慮兩者的大小關系。這裡我們規定兩個堆的大小之差不超過1。先判斷堆頂數和新數的大小關系，有以下三種情況：

最小堆堆頂小於新插入的數時，說明新插入的數處在所有數的上半部分；最大堆堆頂大於新插入的數時，說明新插入的數處在所有數的下半部分；最小堆堆頂大於新插入的數時，但最大堆堆頂小於新插入的數時，說明新插入的數將處在最小堆堆頂或最大堆堆頂，也就是在中間的位置。

再判斷兩個堆的大小關系，如果新插入的數屬於前兩種情況，開始插入目標堆，此時又有兩種操作：

若目標堆不大於另一個堆時，將新數插入目標堆；若目標堆大於另一個堆時，將目標堆的堆頂先移動到另一個堆，再把新數插入目標堆。

如果新插入的數屬於第三種情況，即在中間位置，則插入到大小較小的那個堆即可。這樣，每次新加進來一個數以後，若兩個堆一樣大，則中位數是兩個堆頂的平均值，否則較大的那個堆的堆頂為中位數。

建立兩個堆所用的代碼比較長，而使用優先隊列來實現則簡單許多。

priority_queue：優先隊列，是一個擁有權值概念的單向隊列，在這個隊列中，所有元素是按優先級排列的。優先隊列有兩種，一種是最大優先隊列；一種是最小優先隊列；每次取自隊列的第一個元素分別是優先級最大和優先級最小的元素。

實際使用時，加入頭文件："queue.h", "functional.h"

其中”functional.h”定義了優先級。（若要自己定義優先級可以不加）
三. 示例代碼

class MedianFinder 
{
private: 
    priority_queue, std::greater> q1; // 數據越小，優先級越高
    priority_queue 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();

四. 小結

重新認真學了一下優先隊列，受益匪淺。