作者sean72 (.)
看板Python
标题[问题] leetcode sliding window median
时间Mon Oct 9 08:04:18 2017
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://webptt.com/cn.aspx?n=bbs/Python/M.1507507492.A.40B.html
1F：推 flarehunter: heap的remove应该是O(log n)吧？你要不要自己实作he 10/09 10:14
2F：→ flarehunter: ap看看 10/09 10:14
python heapq 没有办法从heap里面移除单一元素
你说的应该是从堆顶移除元素的复杂度(移除堆顶，然後sift up)
java priorityQueue有remove 但是O(n)
※ 编辑: sean72 (172.89.32.145), 10/09/2017 12:39:30
3F：推 ckc1ark: 我印象中heapq是有个_siftup 不过leetcode不给用XD 10/09 23:30
4F：推 edwar: 楼主程式我调整成自写的remove可从1.09s->0.2s,真的建议自 10/09 23:52
5F：→ edwar: 己实作. 10/09 23:52
7F：→ ckc1ark: 不过我是用Counter 他是用set 10/10 00:38