作者pokkys (人很好那一个)
看板Python
标题Re: [问题] leetcode sliding window median
时间Mon Oct 9 19:20:45 2017
※ 引述《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://webptt.com/cn.aspx?n=bbs/Python/M.1507548049.A.0A9.html
1F：→ ddchris: bisect.insort 似乎是用二元搜寻树走访的方式插入数值, 10/09 19:43
2F：→ ddchris: 比每次都重新排序快的多 10/09 19:44
3F：→ sean72: 这连结打开之後跳转到leetcode 没有程式码 可否贴到其他 10/09 23:57
4F：→ sean72: 分享程式码的网站？ 10/09 23:57