作者edwar (海边的野孩子)
看板Python
标题Re: [问题] leetcode sliding window median
时间Tue Oct 10 01:42:32 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)时间
我把自己实作的heap remove贴在下面
原po只要把
maxheap.remove(-kick)
heapify(maxheap)
和
minheap.remove(kick)
heapify(minheap)
分别改成 heapremove1(maxheap, -kick) 和 heapremove1(minheap, kick) 就可以了.
我自己急就章刻的程式搭配这个remove的原型在leetcode跑409ms.
(
https://leetcode.com/submissions/detail/122733769/ 可能要登入才能看)
所以用你的程式执行时间应该也会落在 410ms 左右.
这个程式在资料量大的情况应该有可能比你说的 mur mur 那个解法更快.
我用
import random, time
random.seed()
nums = []
for i in range(10000):
nums.append(random.randint(-300,300))
k=5000
这样的测试资料, mur mur 的解法大约跑 0.32s (电脑不快, 跑得有点喘)
用这个 heap remove 则是 0.2s.
----
def heapremove1(hp, kick):
i = hp.index(kick)
hp[i] = -float("inf")
m = len(hp)
i_n = i
while (i <= int((m-1)/2) ):
i_n = i*2+1
if i*2+2 < m:
if (hp[i]<=hp[i*2+1]) and (hp[i]<=hp[i*2+2]):
break
if hp[i*2+1] <= hp[i*2+2]:
i_n = i*2+1
else:
i_n = i*2+2
elif i*2+1 < m:
if (hp[i]<=hp[i*2+1]):
break
i_n = i*2+1
else:
break
(hp[i], hp[i_n]) = (hp[i_n], hp[i])
i = i_n
while (i>0):
i_n = int((i-1)/2)
if (hp[i_n]<=hp[i]):
break
(hp[i], hp[i_n]) = (hp[i_n], hp[i])
i = i_n
heappop(hp)
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.36.69.134
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Python/M.1507570954.A.B03.html
※ 编辑: edwar (114.36.69.134), 10/10/2017 01:47:09
※ 编辑: edwar (114.36.69.134), 10/10/2017 10:27:44