480. Sliding Window Median
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples:
[2,3,4], the median is3[2,3], the median is(2 + 3) / 2 = 2.5
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position Median
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
Therefore, return the median sliding window as [1,-1,-1,3,5,6].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
Solution: Heap & HashSet
import heapq
class MinHeap:
def __init__(self):
self.q = []
self.nums = dict()
self.size = 0
def __len__(self):
return self.size
def add(self, num):
if num not in self.nums:
heapq.heappush(self.q, num)
self.nums[num] = 1
else:
self.nums[num] += 1
self.size += 1
def remove(self, num):
if num not in self.nums:
return
self.nums[num] -= 1
if self.nums[num] == 0:
del self.nums[num]
while self.q and self.q[0] not in self.nums:
heapq.heappop(self.q)
self.size -= 1
def top(self):
return self.q[0]
def pop(self):
num = self.top()
self.remove(num)
return num
class MaxHeap(MinHeap):
def add(self, num):
MinHeap.add(self, -num)
def remove(self, num):
MinHeap.remove(self, -num)
def top(self):
return -MinHeap.top(self)
class MedianFinder:
def __init__(self):
self.left = MaxHeap()
self.right = MinHeap()
def add(self, num):
if len(self.left) > 0 and num <= self.left.top():
self.left.add(num)
if len(self.left) > len(self.right) + 1:
self.right.add(self.left.pop())
else:
self.right.add(num)
if len(self.right) > len(self.left) + 1:
self.left.add(self.right.pop())
def remove_add(self, remove_num, add_num):
if remove_num == add_num:
return
if len(self.left) > 0 and remove_num <= self.left.top():
self.left.remove(remove_num)
else:
self.right.remove(remove_num)
self.add(add_num)
def median(self):
if len(self.left) == len(self.right):
return (self.left.top() + self.right.top()) / 2.0
if len(self.left) > len(self.right):
return self.left.top() / 1.0
return self.right.top() / 1.0
class Solution(object):
def medianSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[float]
"""
finder = MedianFinder()
for idx in xrange(k):
finder.add(nums[idx])
medians = [finder.median()]
for idx in xrange(k, len(nums)):
finder.remove_add(nums[idx - k], nums[idx])
medians.append(finder.median())
return medians
Lessons:
- The difficulty is to delete an element from a heap. Just do a lazy deletion, which means only delete it when it's at the top. Otherwise, use a hash set to remember it is a deleted element. This same technique is also used in Skyline problem.
- Another difficulty is to find the actual length of a heap, which should exclude all deleted elements.
- Time complexity is . Because our heap can be size of n if every deletion fail. To make it , we need a tree structure that can remove and rebalance in time.