leetcode hard : Find Median from Data Stream

https://leetcode.com/problems/find-median-from-data-stream/

Find Median from Data Stream - LeetCode

 

일단 보자마자 생각나는건 AVL 트리인데.. 상수조건을 보자.

call이 최대 50000번 일어날 수 있다. 그니까 한 번의 call당 log N 정도면 합격선이다.

잠깐 ! Follow-up이 있다. 두근두근..

Follow up: If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution? If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

중복숫자가 많으면 어떻게 optimize할거냐는 질문같다.

 

포인트는 힙에 있다.

"힙? 힙으로 어떻게 풀어? median인데?"

힙을 꼭 하나만 쓰란법은 없다.

minheap과 maxheap을 준비한다. (눈치빠른 사람들이라면 여기서 벌써 어떻게 푸는건지 감이 올것이다.)

이때 새로운 넘버가 들어오면 minheap과 maxheap사이즈가 같거나 maxheap이 1많게 유지시켜주면서 넣으면 된다.

minheap쪽에 큰 값들을 넣어야 되고 maxheap에 작은값들을 넣어야된다.

maxheap의 root값이 A, minheap의 루트값이 B라고 하자.

새 값 X가 들어오면 세 가지 시나리오가 있을 수 있다.

1. A < X < B -> 둘중 사이즈가 더 작은 곳에 푸시, 사이즈가 같으면 maxheap에 푸시

2. X <= A -> maxheap에 넣고 힙 균형 조절

3. X >= B -> minheap에 넣고 힙 균형 조절

 

class MedianFinder:
    def __init__(self):
        self.small = []  # the smaller half of the list, max heap (invert min-heap)
        self.large = []  # the larger half of the list, min heap

    def addNum(self, num):
        if len(self.small) == len(self.large):
            heappush(self.large, -heappushpop(self.small, -num))
        else:
            heappush(self.small, -heappushpop(self.large, num))

    def findMedian(self):
        if len(self.small) == len(self.large):
            return float(self.large[0] - self.small[0]) / 2.0
        else:
            return float(self.large[0])

addNum -> O(log N)

findMedian -> O(1)