題目

中位數(shù)是有序列表中間的數(shù)。如果列表長(zhǎng)度是偶數(shù)，中位數(shù)則是中間兩個(gè)數(shù)的平均值。
例如，[2,3,4] 的中位數(shù)是 3；[2,3] 的中位數(shù)是 (2 + 3) / 2 = 2.5
設(shè)計(jì)一個(gè)支持以下兩種操作的數(shù)據(jù)結(jié)構(gòu)：
void addNum(int num) - 從數(shù)據(jù)流中添加一個(gè)整數(shù)到數(shù)據(jù)結(jié)構(gòu)中。
double findMedian() - 返回目前所有元素的中位數(shù)。
示例：

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

進(jìn)階:
如果數(shù)據(jù)流中所有整數(shù)都在 0 到 100 范圍內(nèi)，你將如何優(yōu)化你的算法？
如果數(shù)據(jù)流中 99% 的整數(shù)都在 0 到 100 范圍內(nèi)，你將如何優(yōu)化你的算法？

來源：力扣（LeetCode）
鏈接：Leetcode295 數(shù)據(jù)流中的中位數(shù)

思路

優(yōu)化解法，動(dòng)態(tài)維護(hù)一個(gè)最大堆和一個(gè)最小堆。各存放一半數(shù)據(jù)，要求：最大堆的堆頂元素要比最小堆的堆頂元素小(這樣，最大堆里面的元素都比最小堆里面的值小)。

priority_queue<int> big_queue;//默認(rèn)最大堆priority_queue< int,vector<int>,greater<int>> small_queue;//最小堆構(gòu)造

按照最大堆和最小堆中元素個(gè)數(shù)分為三種情況討論：無非相等，最大堆元素多一個(gè)，最小堆元素對(duì)一個(gè)三種情況。當(dāng)新來的元素num來的時(shí)候，即遇到如下三種情況分析：

最大堆大小==最小堆大小

最大堆大小＞最小堆

最大堆大小＜最小堆

使之滿足最小堆和最大堆滿足：元素個(gè)數(shù)相等，或者最大堆元素多一個(gè)，或者最小堆元素多一個(gè)。這樣中位數(shù)便可以在堆頂元素取得。無非是取平均值或者某一個(gè)堆頂元素。

代碼

class MedianFinder { public:/** initialize your data structure here. */MedianFinder() {}void addNum(int num) {if(big_queue.empty())//堆為空時(shí)，這里其實(shí)保證了兩個(gè)隊(duì)大小基本一樣{big_queue.push(num);return;}if(big_queue.size()==small_queue.size())//最大堆大小==最小堆大小{if(num<big_queue.top())big_queue.push(num);elsesmall_queue.push(num);}else if(big_queue.size()>small_queue.size())//最大堆大小＞最小堆{if(num>big_queue.top())small_queue.push(num);else {small_queue.push(big_queue.top());big_queue.pop();big_queue.push(num);}}else if(big_queue.size()<small_queue.size())//最大堆大小＜最小堆{if(num>small_queue.top()){small_queue.push(num);big_queue.push(small_queue.top());small_queue.pop();}else{big_queue.push(num);}}}double findMedian() {if(big_queue.size()==small_queue.size())//偶數(shù)時(shí)，返回兩者平均值return (small_queue.top()+big_queue.top())/2.0;else if(big_queue.size()>small_queue.size())return big_queue.top();return small_queue.top();}private:priority_queue<int> big_queue;priority_queue< int,vector<int>,greater<int>> small_queue; };/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

測(cè)試結(jié)果：

總結(jié)

最小堆和最大堆結(jié)合，這樣可以提高算法速度。比直觀的使用數(shù)組排序并且查找中位數(shù)要快很多。

總結(jié)

以上是生活随笔為你收集整理的Leetcode295 数据流中的中位数-最小堆和最大堆的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。