[問題] leetcode sliding window median

[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)時間

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 172.89.32.145
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1507507492.A.40B.html
推 flarehunter: heap的remove應該是O(log n)吧？你要不要自己實作he
→ flarehunter: ap看看
python heapq 沒有辦法從heap裡面移除單一元素
你說的應該是從堆頂移除元素的複雜度(移除堆頂，然後sift up)

java priorityQueue有remove 但是O(n)
※ 編輯: sean72 (172.89.32.145), 10/09/2017 12:39:30
推 ckc1ark: 我印象中heapq是有個_siftup 不過leetcode不給用XD
推 edwar: 樓主程式我調整成自寫的remove可從1.09s->0.2s,真的建議自
→ edwar: 己實作.
推 ckc1ark: 看到有人像我用lazy remove http://tinyurl.com/ybmpn74j
→ ckc1ark: 不過我是用Counter 他是用set