如何得到一個數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值。

例如，

• [2,3,4] 的中位數(shù)是 3

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

設(shè)計一個支持以下兩種操作的數(shù)據(jù)結(jié)構(gòu)：

• void addNum(int num) - 從數(shù)據(jù)流中添加一個整數(shù)到數(shù)據(jù)結(jié)構(gòu)中。

• double findMedian() - 返回目前所有元素的中位數(shù)。

示例1

• 輸入：

["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]

[[],[1],[2],[],[3],[]]

• 輸出：

[null,null,null,1.50000,null,2.00000]

限制

• 最多會對 addNum、findMedian 進行 50000 次調(diào)用。

方法：優(yōu)先隊列

• MedianFinder：

• 我們創(chuàng)建兩個優(yōu)先隊列，分別保存列表的一半：

• 小頂堆，保存值較大的一半；

• 大頂堆，保存值較小的一半；

• addNum：

• 為偶數(shù)時，向大頂堆中加入當(dāng)前值，再將大頂堆的堆頂元素插入到小頂堆；

• 為奇數(shù)時，向小頂堆中加入當(dāng)前值，再將小頂堆的堆頂元素插入到大頂堆；

• findMedian：

• 為偶數(shù)時，中位數(shù)取兩個堆頂元素之和除以2；

• 為奇數(shù)時，中位數(shù)取小頂堆的堆頂元素。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度：

• addNum: O(logn)，其中 n 為累計添加的數(shù)的數(shù)量。

• findMedian: O(1)。

• 空間復(fù)雜度：O(n)，主要為優(yōu)先隊列的開銷。

END

騏驥一躍，不能十步；駑馬十駕，功在不舍；鍥而舍之，朽木不折；鍥而不舍，金石可鏤，贈友人。

好兄弟可以點贊并關(guān)注我的公眾號“javaAnswer”，全部都是干貨。