※ 引述《sean72 (.)》之銘言：
: https://leetcode.com/problems/sliding-window-median/description/
我先說，這不是我的答案。
大方向就是，移動window的過程，就是先減一個, 再加一個
他減一個的方法是O(k), 加一個的方法是O(log k)
整個過程是O(n * k)
class Solution(object):
def medianSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[float]
"""
window = sorted(nums[:k])
medians = []
for a, b in zip(nums, nums[k:] + [0]):
medians.append((window[k/2] + window[~(k/2)]) / 2.)
window.remove(a)
bisect.insort(window, b)
return medians
我自己的作法是把insort換成append -> sorted
沒想到也會過....
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.70.68.42
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1507568121.A.04B.html
※ 編輯: pokkys (61.70.68.42), 10/10/2017 00:59:43