活跃农民
- 积分
- 927
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2019-2-2
- 最后登录
- 1970-1-1
|
- class Solution:
- def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
-
- def move(h1, h2):
- x, i = heapq.heappop(h1)
- heapq.heappush(h2, (-x, i))
- def getMedian(h1, h2, k):
- return h2[0][0] * 1. if k % 2 == 1 else (h2[0][0]-h1[0][0]) / 2.
-
- small, large = [], []
- for i, x in enumerate(nums[: k]):
- heapq.heappush(small, (-x, i))
-
- for _ in range(k - (k >> 1)):
- move(small, large)
-
- ans = [getMedian(small, large, k)]
-
- for i, x in enumerate(nums[k:]):
- if x >= large[0][0]:
- heapq.heappush(large, (x, i + k))
- if nums[i] <= large[0][0]:
- move(large, small)
- else:
- heapq.heappush(small, (-x, i + k))
- if nums[i] >= large[0][0]:
- move(small, large)
- while small and small[0][1] <= i:
- heapq.heappop(small)
- while large and large[0][1] <= i:
- heapq.heappop(large)
- ans.append(getMedian(small, large, k))
- return ans
复制代码
Why is deletion for 2 heaps O(n)? This solution uses lazy deletion for both small heap and large heap, but removal from a heap should still be O(logN) right?
Here is my other solution using SortedList. sortedcontainers is not a standard library in python but it's included in leetcode environment. I believe java has treeset and cpp has multiset which does similar things.
- class Solution:
- def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
- from sortedcontainers import SortedList
- result = []
- sortedList = SortedList()
- start = nums[: k]
- for a in start:
- sortedList.add(a)
-
- def getMedian(sortedList):
- if k % 2 == 1:
- return sortedList[k // 2]
- else:
- return (sortedList[k // 2] + sortedList[k // 2 - 1]) / 2.0
-
- result.append(getMedian(sortedList))
- n = len(nums)
- for i in range(n - k):
- to_remove_index = sortedList.bisect_left(nums[i])
- sortedList.pop(to_remove_index)
- sortedList.add(nums[i + k])
- result.append(getMedian(sortedList))
-
- return result
复制代码 [/i][/i][/i] |
|