題目描述
如何得到一個數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值泞遗，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值殷蛇。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值戒幔。我們使用Insert()方法讀取數(shù)據(jù)流，使用GetMedian()方法獲取當前讀取數(shù)據(jù)的中位數(shù)土童。
思路
第一種思路诗茎，把全部元素存下來，排序献汗，取中位數(shù)敢订。如果數(shù)據(jù)量太大的情況下，效率較低罢吃。
第二種思路楚午，使用最大堆和最小堆來解決。
首先構(gòu)建一個最大堆和一個最小堆尿招，
隨后不斷接收數(shù)據(jù)流里的數(shù)據(jù)矾柜，每接收一個，將其插入到堆里面泊业。同時調(diào)整兩個堆里元素的數(shù)量把沼，保證兩個堆的數(shù)據(jù)差在一個之內(nèi)。
python里有內(nèi)置的heapq可以使用吁伺，但是這個heap是最小堆饮睬，所以還要創(chuàng)建一個最大堆。這里最大堆的創(chuàng)建方法在GitHub上學到了一個小技巧篮奄，把應(yīng)該加入最大堆的元素取相反數(shù)捆愁，然后加入到最小堆。那么這個裝滿相反數(shù)的最小堆就可以看成一個最大堆窟却。很巧妙的一個方法昼丑。
代碼
class Solution:
def __init__(self):
self.left = []
self.right = []
def Insert(self, num):
from heapq import heappush, heappop
#left 大堆 right 小堆
if len(self.right) == 0 or num > self.right[0]:
heappush(self.right, num)
else:
# push num的相反數(shù)進去，雖然left還是最小堆夸赫，但是里面的值都是相反數(shù)菩帝，反過來就是最大堆
heappush(self.left, -num)
# 不斷調(diào)整兩個堆，保證左右兩個堆里元素的數(shù)量平衡
while len(self.left) - len(self.right) > 1:
data = -heappop(self.left)
heappush(self.right, data)
while len(self.right) - len(self.left) > 1:
data = heappop(self.right)
heappush(self.left, -data)
def GetMedian(self,xxx):
if len(self.left) == len(self.right):
if len(self.right) == 0:
return 0
min_heap = self.right[0]
max_heap = -1*self.left[0]
media = (min_heap+max_heap)/2.0
return media
elif len(self.left) > len(self.right):
media = -1*self.left[0]
return media
else:
return self.right[0]
