題目描述

如何得到一個數(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上學(xué)到了一個小技巧，把應(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]