2019-08-24 劍指 數(shù)據(jù)流中的中位數(shù)

30min,在 python的heapq中只有最小堆,沒有最大堆,可以取-值,但是有點麻煩,很容易錯??梢苑庋b一下。邏輯沒錯,就是最大堆的處理會麻煩

from heapq import *
class Solution:
    def __init__(self):
        self.cnt=0
        self.maxlist=[]
        self.minlist=[]

    def Insert(self, num):
        self.cnt+=1
        if self.cnt%2==1: # 加入左邊
            if self.minlist and num>self.minlist[0]:
                heappush(self.maxlist,-heappop(self.minlist)) #-
                heappush(self.minlist,num)
            else:heappush(self.maxlist,-num) #-
        else:  # 加入右邊
            if num<-self.maxlist[0]: # 這里要變成-
                heappush(self.minlist,-heappop(self.maxlist)) # - 同時pop寫成了push
                heappush(self.maxlist,-num)
            else:heappush(self.minlist,num)

    def GetMedian(self,n):
        if self.cnt==0:return 0
        if self.cnt%2==0:return (self.minlist[0]-self.maxlist[0])/2.0
        else:return -self.maxlist[0]
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點,簡書系信息發(fā)布平臺,僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • Heap in python Heap,即堆,也就是優(yōu)先隊列。我們可以在這里找到[]維基百科](https://e...
    英武閱讀 2,874評論 0 51
  • 題目描述 如何得到一個數(shù)據(jù)流中的中位數(shù)?如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值,那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值...
    Max_7閱讀 1,155評論 0 0
  • 人生中,我們都會遇到很多選擇的機(jī)會,小到交通工具,大到人生伴侶,事業(yè)投資……等等 去某個地方,是選擇飛機(jī)還是火車?...
    愛一茶江泳閱讀 139評論 0 0
  • - 我是個“網(wǎng)癮少女”,所以我在網(wǎng)上看到的故事、信息比同齡人要多的多。 因為我“來者不拒”,所以看到故事里面既有男...
    DIPPER星閱讀 230評論 0 1
  • 早睡早起: 7/7(6:00~23:00) 健康飲食: 7/7(蒸雜糧蔬菜飯,雞蛋,蝦,魚) 運動: 2/7(45...
    馬潤芳閱讀 70評論 0 0

友情鏈接更多精彩內(nèi)容