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:
<code>[2,3,4]</code> , the median is <code>3</code>
<code>[2,3]</code>, the median is <code>(2 + 3) / 2 = 2.5</code>
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:
Credits:
這道題給我們一個資料流，讓我們找出中位數，由于資料流中的資料并不是有序的，是以我們首先應該想個方法讓其有序。如果我們用vector來儲存資料流的話，每進來一個新資料都要給數組排序，很不高效。是以之後想到用multiset這個資料結構，是有序儲存資料的，但是它不能用下标直接通路元素，找中位數也不高效。這裡用到的解法十分巧妙，我們使用大小堆來解決問題，其中大堆儲存右半段較大的數字，小堆儲存左半段較小的數組。這樣整個數組就被中間分為兩段了，由于堆的儲存方式是由大到小，我們希望大堆裡面的資料是從小到大，這樣取第一個來計算中位數友善。我們用到一個小技巧，就是存到大堆裡的數先取反再存，這樣由大到小存下來的順序就是實際上我們想要的從小到大的順序。當大堆和小堆中的數字一樣多時，我們取出大堆小堆的首元素求平均值，當小堆元素多時，取小堆首元素為中位數，參見代碼如下：
解法一：
上述方法是用priority_queue來實作堆功能的，下面我們還可用multiset來實作堆，參見代碼如下：
解法二：