※ 引述《sean72 (.)》之銘言：
: https://leetcode.com/problems/sliding-window-median/description/
: leetcode裡面python解法對我來說有點玄
: (mur mur 那個解法提供者的python code每次都短到爆，而且很難讀懂 T_T)
: 有人知道這題python該怎麼解嗎?
: 我的解法 參考網路上搜到的java解法
: https://repl.it/MSNr/3
: 維持左邊一個maxheap, 右邊一個minheap
: median為maxheap top
: 每次window往右滑動，則判斷新數字大於或是小於media，
: 往左邊或是右邊的heap加入一個元素
: 並且減去剛剛脫離window那個數字
: 但是會超時
: 我猜我的瓶頸應該是在remove之後重新heapify ，這裡需要O(klogk)
: java用treeset or priorityQueue remove只需要O(k)時間
我把自己實作的heap remove貼在下面
原po只要把
maxheap.remove(-kick)
heapify(maxheap)
和
minheap.remove(kick)
heapify(minheap)
分別改成 heapremove1(maxheap, -kick) 和 heapremove1(minheap, kick) 就可以了.
我自己急就章刻的程式搭配這個remove的原型在leetcode跑409ms.
( https://leetcode.com/submissions/detail/122733769/ 可能要登入才能看)
所以用你的程式執行時間應該也會落在 410ms 左右.
這個程式在資料量大的情況應該有可能比你說的 mur mur 那個解法更快.
我用
import random, time
random.seed()
nums = []
for i in range(10000):
nums.append(random.randint(-300,300))
k=5000
這樣的測試資料, mur mur 的解法大約跑 0.32s (電腦不快, 跑得有點喘)
用這個 heap remove 則是 0.2s.