題目描述

如何得到一個數據流中的中位數？如果從數據流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值。如果從數據流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值。我們使用Insert()方法讀取數據流，使用GetMedian()方法獲取當前讀取數據的中位數。

解題思路

一般數據流我們用數組來表示，要得到中位數有很多種方法，這里介紹一種時間復雜度較小的方法，用C++種的優先級隊列。
也就是劍指offer書上的方法，把數組邏輯上分成兩個部分，左邊為最大堆，右邊為最小堆。我們始終要保證最大堆中最大的元素要小于最小堆中最小的元素即可，當然除此之外，還要判斷數組中元素個數是偶數還是奇數，如果要判斷我們必須要讓兩個堆中的元素個數之差不大于1，在這里，我們保證最大堆的元素個數可以等于最小堆元素個數+1，但是最小堆堆元素個數最多只能與最大堆相同。 那么如果兩個堆的元素個數相同，那么就是偶數，那么中位數就是兩個堆頂元素之和除以2，如果不相同的話，說明最大堆的元素個數多，取最大堆堆頂元素即可。

代碼實現

class Solution {priority_queue<int,vector<int>,less<int>> max;priority_queue<int,vector<int>,greater<int>> min;
public:void Insert(int num){if(max.empty() || num<= max.top())max.push(num);elsemin.push(num);//保證兩個堆的元素個數之差小于1if(max.size() == min.size()+2){min.push(max.top());max.pop();}if(max.size()+1 == min.size()){max.push(min.top()); min.pop();}}double GetMedian(){ return max.size() == min.size() ? (max.top()+min.top())/2.0 : max.top();}};