Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-heap
class MedianFinder:
"""
Problem Clarification
If it is a steam (dynamically update/delete/add array)?
-> Yes
Thought Process
Brute Force:
step1: maintain a array by each time we called addnum, we sorted again. ->O(nlogn)
or
maintain a array by each time we called addnum
find insertion position using bs, O(logn)
insert num into array O(n)
step2: calcuate median by
if list is odd we return A[n//2]
if list is even we return (A[n//2]+A[n//2-1])/2
-> O(1)
[1,2]
[2,3,4]
[2,3,4,5]
1 2
PQ:
we need two PQ. one is min-heap and the other one is max-heap.
min-heap放比中位數大的數字,max-heap放比中位數小的數字, 因爲中位數右半邊的數放在min-heap,我才可以知道min-heap的Root是最接近中位數的那個數. 反之中位數左半邊的數放在max-heap, 我就可以知道max-heap的root是最接近中位數的那個數。
step1: maintain two PQ and need to balanced abs(size of left pq-size of righ_pq) <1
"""
def __init__(self):
"""
initialize your data structure here.
"""
self.A = []
def addNum(self, num: int) -> None:
"""
O(nlogn)
"""
self.A.append(num)
self.A = sorted(self.A)
def findMedian(self) -> float:
"""
O(1)
"""
n = len(self.A)
if n % 2 == 1:
return self.A[n//2]
else:
print (n//2)
return (self.A[n//2]+self.A[n//2-1])/2
class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.right_min_heap = []
self.left_max_heap = []
def balance(self):
if len(self.left_max_heap) - len(self.right_min_heap) ==2:
#把左邊最大的元數拿出來放到右邊
data = heapq.heappop(self.left_max_heap)
heapq.heappush(self.right_min_heap, -data)
return
if len(self.left_max_heap) < len(self.right_min_heap):
#把右邊最小的元數拿出來放到左邊
data = heapq.heappop(self.right_min_heap)
heapq.heappush(self.left_max_heap, -data)
return
def addNum(self, num: int) -> None:
"""
O(logn)
During the process, we want to make sure len(self.left_max_heap) >= len(self.righ_min_heap)
Also, we to balance right and left pq.
"""
if len(self.left_max_heap)==0:
heapq.heappush(self.left_max_heap, -num)
return
if num <= -self.left_max_heap[0]:
heapq.heappush(self.left_max_heap, -num)
else:
heapq.heappush(self.right_min_heap, num)
# balance left/right
self.balance()
def findMedian(self) -> float:
"""
O(1)
"""
median = None
if len(self.left_max_heap) > len(self.right_min_heap):
# odd
median = -self.left_max_heap[0]
else:
# even
median = (-self.left_max_heap[0]+ self.right_min_heap[0]) / 2
return median
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment