295. Find Median from Data Stream

 1# (wrong) idea: likely math
 2# [2] -> 2
 3# [2,3] -> 2.5
 4# [2,3,4] -> we just drop 2, keep and return 3 -> [3, 4] -> 3
 5# [2,3,4,1] ->
 6
 7# another idea: heap/sorted list (n log n)
 8
 9# ideal: two-heap, one for lower half, one for upper half
10
11class MedianFinder:
12
13    def __init__(self):
14        self.lo, self.hi = [], []  # max heap, min heap
15
16    def addNum(self, num: int) -> None:
17        heapq.heappush(self.lo, -num)
18
19        if self.lo and self.hi and (-self.lo[0] > self.hi[0]):
20            heapq.heappush(self.hi, -heapq.heappop(self.lo))
21        if len(self.lo) < len(self.hi):
22            heapq.heappush(self.lo, -heapq.heappop(self.hi))
23        if len(self.lo) > len(self.hi) + 1:
24            heapq.heappush(self.hi, -heapq.heappop(self.lo))
25
26    def findMedian(self) -> float:
27        if len(self.lo) > len(self.hi):
28            return -self.lo[0]
29        return (-self.lo[0] + self.hi[0]) / 2.0
30
31
32# Your MedianFinder object will be instantiated and called as such:
33# obj = MedianFinder()
34# obj.addNum(num)
35# param_2 = obj.findMedian()