[問題] leetcode sliding window median

看板Python作者sean72 (.)時間8年前 (2017/10/09 08:04)推噓4(4推 0噓 3→)

留言7則, 3人參與討論串1/4 (看更多)

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

10/09 10:14, 8年前 , 1^F

10/09 10:14, 1^F

→

flarehunter

10/09 10:14, 8年前 , 2^F

10/09 10:14, 2^F

python heapq 沒有辦法從heap裡面移除單一元素你說的應該是從堆頂移除元素的複雜度(移除堆頂，然後sift up) java priorityQueue有remove 但是O(n) ※ 編輯: sean72 (172.89.32.145), 10/09/2017 12:39:30

推

ckc1ark

10/09 23:30, 8年前 , 3^F