Re: [問題] 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)時間
我這樣寫竟然沒有超時.....
https://tinyurl.com/yckavkzx
我有看到別人，把我用sorted的部份換成bisect.insort
速度變超快
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.70.68.42
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1507548049.A.0A9.html
→
10/09 19:43,
8年前
, 1F
10/09 19:43, 1F
→
10/09 19:44,
8年前
, 2F
10/09 19:44, 2F
→
10/09 23:57,
8年前
, 3F
10/09 23:57, 3F
→
10/09 23:57,
8年前
, 4F
10/09 23:57, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 4 篇)：