1.題目要求

中位數是有序列表中間的數。如果列表長度是偶數，中位數則是中間兩個數的平均值。

例如，

[2,3,4]?的中位數是 3

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

設計一個支持以下兩種操作的數據結構：

• void addNum(int num) - 從數據流中添加一個整數到數據結構中。
• double findMedian() - 返回目前所有元素的中位數。

示例：

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

進階:

如果數據流中所有整數都在 0 到 100 范圍內，你將如何優化你的算法？

如果數據流中 99% 的整數都在 0 到 100 范圍內，你將如何優化你的算法？

?

?

2.解題思路

堆是一個非常重要的數據結構，堆排序在C++中的實現為優先級隊列(Priority_queue），關于這一點，我的另一篇博文 "Leetcode 703. 數據流中的第K大元素"? 有更詳細提到，這里不做重復。

LeetCode網站把這一道劃分在“堆”一類中，也是提醒我們使用堆結構。這道題很巧妙，我是聽了算法課（牛客網的左程云大牛）的講解才弄明白。這里的代碼是自己聽懂了思路，獨立寫出來的。

關鍵思路：建立兩個堆（使用priority_queue實現），一個大根堆，一個小根堆。

? ? ? ? ? （1）一個大根堆，保存所有整數中較小的1/2;一個小根堆，保存所有整數中較大的1/2；
????????? （2）并且，依次添加元素過程中，兩個堆元素個數的差的絕對值不能超過1；

? ? ? ? ? ? ? ?? 這樣，兩個堆建立好了以后，

? ? ? ? ? （1）如果輸入的元素個數 n 是偶數，則兩個堆的元素個數相等，分別取大根堆的頂和小根堆的頂，取平均值，即是所求的整個數據流的中位數；

? ? ? ? ? （2）如果輸入的元素個數 n 是奇數，則必有一個堆的元素個數為（n/2+1），返回這個堆的頂，即為所求的中位數。

?

3.我的代碼

? ? ? ? 個人比較喜歡寫段落注釋和行注釋，因為這樣自己一年之后還能快速看懂，當然也方便他人，特別是一起刷題的伙伴，輕松看懂。

? ? ? ? 更多的細節講解里都在注釋里。如有錯誤的地方，歡迎多指正。

? ? ? ? 代碼通過所有測試案例的時間為124ms。 ? ? ? ?

class MedianFinder { public:/** initialize your data structure here. */MedianFinder() {}void addNum(int num) {/*建立兩個堆：（1）一個大根堆，保存所有整數中較小的1/2;一個小根堆，保存所有整數中較大的1/2;（2）并且，依次添加元素過程中，兩個堆大小的差的絕對值不能超過1； *///第一元素加入大根堆if(heap1.size()==0){heap1.push(num);return;}if(num<=heap1.top()){//第二個元素比大根堆的頂小 heap1.push(num);//大根堆元素過多if(heap1.size()-heap2.size()>1){int temp = heap1.top();heap1.pop();heap2.push(temp);//大根堆彈出頂到小根堆 }}else{//第二個元素比大根堆的頂大，直接進入小根堆 heap2.push(num);//小根堆元素過多if(heap2.size()-heap1.size()>1){int temp = heap2.top();heap2.pop();heap1.push(temp);//小根堆彈出頂到大根堆 }}}double findMedian() {//輸入的元素為奇數個if(heap1.size() > heap2.size())return heap1.top();else if(heap1.size() < heap2.size())return heap2.top();//輸入的元素個數為偶數elsereturn (heap1.top()+heap2.top())/2.0; //取大根堆、小根堆的堆頂元素取平均值，即為所求全局中位數 }private:priority_queue<int> heap1;//默認，大根堆priority_queue<int,vector<int>,greater<int>> heap2;//小根堆（升序序列） };/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

??

4.用時更少的示例代碼

?這是我提交解答后，查看細節，看到的Leetcode官網上提交的關于這道題運行時間最短（96ms）的示例代碼。

?LeetCode上刷好多速度排名第一的代碼中都有一段類似的代碼，就是下面代碼中的第一段代碼——優化C++的IO速度。

/*一般地，C++的運行速度不如C的，主要原因是C++的輸入輸出流兼容了C的輸入輸出，因此，C++的速度才會變慢，
如果去掉C++的輸入輸出的兼容性的話，速度就和C的差不多了*/
static const auto __ = []() {// turn off syncstd::ios::sync_with_stdio(false);// untie in/out streams std::cin.tie(nullptr);return nullptr; }();class MedianFinder { public:/** initialize your data structure here. *///使用vector實現兩個堆，而不是priority_queuevector<int> maxheap;vector<int> minheap;bool flag = true;MedianFinder() { }void addNum(int num) {if(flag){//構建小根堆if(minheap.size()>0&&num>minheap[0]){minheap.push_back(num);push_heap(minheap.begin(),minheap.end(),greater<int>()); num = minheap[0];pop_heap(minheap.begin(),minheap.end(),greater<int>());minheap.pop_back();}maxheap.push_back(num);push_heap(maxheap.begin(),maxheap.end(),less<int>());flag=false;}else{//構建大根堆if(maxheap.size()>0&&num<maxheap[0]){maxheap.push_back(num);push_heap(maxheap.begin(),maxheap.end(),less<int>());num = maxheap[0];pop_heap(maxheap.begin(),maxheap.end(),less<int>());maxheap.pop_back();}minheap.push_back(num);push_heap(minheap.begin(),minheap.end(),greater<int>()); flag=true;}}double findMedian() {if(maxheap.size()<1&&minheap.size()<1)return 0;if(flag){return (maxheap[0]+minheap[0])/2.0; }else{return maxheap[0];}} };/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

?

參考博客：

? ? ? https://blog.csdn.net/xiaosshhaa/article/details/78136032 ?? std::ios::sync_with_stdio(false); cin.tie(0);

?

轉載于:https://www.cnblogs.com/paulprayer/p/9884332.html

總結

以上是生活随笔為你收集整理的Leetcode 295. 数据流的中位数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。