295. Find Median from Data Stream (Two Pointers, Design, Sorting, Heap (Priority Queue), Data Stream)

링크 - https://leetcode.com/problems/find-median-from-data-stream/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Hard

Intuition

우리는 두개의 Heap을 통해 문제를 풀 수 있다. 하나의 Heap은 Max Heap을 만들어 작은 숫자들을 가장 큰게 맨 앞에 오도록 만들고, Min Heap을 만들어 큰 숫자들을 가장 작은게 맨 앞에 오도록 만든다. 그러면 우리는 Median을 항상 Heap의 가장 앞에 있는 숫자로 구할 수 있다.

Code

class MedianFinder:

    def __init__(self):
        self.lo_heap = [] # Max heap
        self.hi_heap = [] # Min heap(default)
        self.length = 0

    def addNum(self, num: int) -> None:
        self.length += 1

        heapq.heappush(self.hi_heap, -heapq.heappushpop(self.lo_heap, -num))
        if len(self.hi_heap) > len(self.lo_heap):
            heapq.heappush(self.lo_heap, -heapq.heappop(self.hi_heap))
        

    def findMedian(self) -> float:
        if self.length == 0:
            return .0

        if self.length % 2 == 1:
            return -self.lo_heap[0]
        else:
            return (-self.lo_heap[0] + self.hi_heap[0]) / 2
        


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

Complexity

Time Complexity: O(logN) heap의 operation에 걸리는 시간이다.

Space Complexity: O(N)