題目
如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值。我們使用Insert()方法讀取數(shù)據(jù)流，使用GetMedian()方法獲取當(dāng)前讀取數(shù)據(jù)的中位數(shù)。
數(shù)據(jù)范圍：數(shù)據(jù)流中數(shù)個(gè)數(shù)滿足 1≤n≤1000 ，大小滿足 1≤val≤1000 。
進(jìn)階： 空間復(fù)雜度O(n)， 時(shí)間復(fù)雜度O(nlogn)
示例1
輸入：
[5,2,3,4,1,6,7,0,8]
返回值：
"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
說(shuō)明：
數(shù)據(jù)流里面不斷吐出的是5,2,3...,則得到的平均數(shù)分別為5,(5+2)/2,3...
示例2
輸入：
[1,1,1]
返回值：
"1.00 1.00 1.00 "
思路
本題是對(duì)頂堆算法的一個(gè)經(jīng)典題，所謂對(duì)頂堆算法，實(shí)際上就是使用一個(gè)小頂堆和一個(gè)大頂堆（C++中的priority_queue）。
對(duì)于求動(dòng)態(tài)中位數(shù)的問(wèn)題，利用堆的性質(zhì)，可以在O(nlogn)的時(shí)間復(fù)雜度取出最大值或最小值，那么我們可以用大頂堆維護(hù)前一半的數(shù)，用小頂堆維護(hù)后面一半的數(shù)。
規(guī)定若元素總數(shù)為奇數(shù)，那么大頂堆的元素個(gè)數(shù)要比小頂對(duì)的個(gè)數(shù)多1，這樣，當(dāng)總數(shù)為奇數(shù)時(shí)，中位數(shù)就是大頂堆的堆頂元素；當(dāng)總數(shù)為偶數(shù)時(shí)，中位數(shù)就大頂堆堆頂和小頂堆堆頂元素的平均值。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-819837.html
具體做法是，在每次輸入的時(shí)候?qū)?shù)字先加入大頂堆，大頂堆排序后，將大頂堆的最大值彈出加入小頂堆，小頂堆在進(jìn)行排序。為了保持規(guī)定中的平衡，如果大頂堆的大小小于小頂堆，則需要彈出小頂堆的最大值加入大頂堆。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-819837.html
解答代碼
#include <queue>
class Solution {
public:
priority_queue<int> max_top_heap; // 大頂堆，存較小的值
priority_queue<int, vector<int>, greater<int>> min_top_heap; // 小頂堆，存較大的值
void Insert(int num) {
max_top_heap.push(num);
min_top_heap.push(max_top_heap.top());
max_top_heap.pop();
if (max_top_heap.size() < min_top_heap.size()) {
max_top_heap.push(min_top_heap.top());
min_top_heap.pop();
}
}
double GetMedian() {
int size = max_top_heap.size() + min_top_heap.size();
if ((size&1) == 1) {
// 奇數(shù)
return static_cast<double>(max_top_heap.top());
} else {
// 偶數(shù)
return static_cast<double>(
(max_top_heap.top() + min_top_heap.top()) / 2.0);
}
}
};
到了這里，關(guān)于算法進(jìn)階——數(shù)據(jù)流中的中位數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
