forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsliding-window-median.py
113 lines (99 loc) · 3.81 KB
/
sliding-window-median.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
# Time: O(nlogk)
# Space: O(k)
from sortedcontainers import SortedList
class Solution(object):
def medianSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[float]
"""
sl = SortedList(float(nums[i])for i in xrange(k))
result = [(sl[k//2]+sl[k//2-(1-k%2)])/2]
for i in xrange(k, len(nums)):
sl.add(float(nums[i]))
sl.remove(nums[i-k])
result.append((sl[k//2]+sl[k//2-(1-k%2)])/2)
return result
# Time: O(nlogk)
# Space: O(k)
import collections
import heapq
class Solution2(object):
def medianSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[float]
"""
def lazy_delete(heap, to_remove, sign):
while heap and sign*heap[0] in to_remove:
to_remove[sign*heap[0]] -= 1
if not to_remove[sign*heap[0]]:
del to_remove[sign*heap[0]]
heapq.heappop(heap)
def full_delete(heap, to_remove, sign): # Time: O(k), Space: O(k)
result = []
for x in heap:
if sign*x not in to_remove:
result.append(x)
continue
to_remove[sign*x] -= 1
if not to_remove[sign*x]:
del to_remove[sign*x]
heap[:] = result
heapify(heap)
min_heap, max_heap = [], []
for i in xrange(k):
if i%2 == 0:
heapq.heappush(min_heap, -heapq.heappushpop(max_heap, -nums[i]))
else:
heapq.heappush(max_heap, -heapq.heappushpop(min_heap, nums[i]))
result = [float(min_heap[0])] if k%2 else [(min_heap[0]-max_heap[0])/2.0]
to_remove = collections.defaultdict(int)
for i in xrange(k, len(nums)):
heapq.heappush(max_heap, -heapq.heappushpop(min_heap, nums[i]))
if nums[i-k] > -max_heap[0]:
heapq.heappush(min_heap, -heapq.heappop(max_heap))
to_remove[nums[i-k]] += 1
lazy_delete(max_heap, to_remove, -1)
lazy_delete(min_heap, to_remove, 1)
if len(min_heap)+len(max_heap) > 2*k:
full_delete(max_heap, to_remove, -1)
full_delete(min_heap, to_remove, 1)
result.append(float(min_heap[0]) if k%2 else (min_heap[0]-max_heap[0])/2.0)
return result
# Time: O(nlogn) due to lazy delete
# Space: O(n)
import collections
import heapq
class Solution3(object):
def medianSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[float]
"""
def lazy_delete(heap, to_remove, sign):
while heap and sign*heap[0] in to_remove:
to_remove[sign*heap[0]] -= 1
if not to_remove[sign*heap[0]]:
del to_remove[sign*heap[0]]
heapq.heappop(heap)
min_heap, max_heap = [], []
for i in xrange(k):
if i%2 == 0:
heapq.heappush(min_heap, -heapq.heappushpop(max_heap, -nums[i]))
else:
heapq.heappush(max_heap, -heapq.heappushpop(min_heap, nums[i]))
result = [float(min_heap[0])] if k%2 else [(min_heap[0]-max_heap[0])/2.0]
to_remove = collections.defaultdict(int)
for i in xrange(k, len(nums)):
heapq.heappush(max_heap, -heapq.heappushpop(min_heap, nums[i]))
if nums[i-k] > -max_heap[0]:
heapq.heappush(min_heap, -heapq.heappop(max_heap))
to_remove[nums[i-k]] += 1
lazy_delete(max_heap, to_remove, -1)
lazy_delete(min_heap, to_remove, 1)
result.append(float(min_heap[0]) if k%2 else (min_heap[0]-max_heap[0])/2.0)
return result