데이터 스트림에서 중앙값 찾기

중앙값은 정렬된 정수 목록의 중간 값입니다. 목록의 크기가 짝수이면 중간 값이 없으며 중앙값은 두 중간 값의 평균입니다.

예를 들어 arr = [2,3,4] 의 경우 중앙값은 3 입니다.

예를 들어 arr = [2,3] 의 경우 중앙값은 (2 + 3) / 2 = 2.5 입니다.

MedianFinder 클래스를 구현합니다.

MedianFinder()는 MedianFinder 개체를 초기화합니다.

void addNum(int num)는 데이터 스트림의 정수num를 데이터 구조에 추가합니다.

double findMedian()는 지금까지 모든 요소의 중앙값을 반환합니다. 실제 답변의 10-5 이내 답변이 허용됩니다.

예 1:

입력
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
산출
[널, 널, 널, 1.5, 널, 2.0]

설명
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);//도착 = [1]
medianFinder.addNum(2);//도착 = [1, 2]
medianFinder.findMedian();//1.5 반환(즉, (1 + 2)/2)
medianFinder.addNum(3);//도착[1, 2, 3]
medianFinder.findMedian();//2.0 반환

제약:

-105 <= num <= 105

findMedian 를 호출하기 전에 데이터 구조에 하나 이상의 요소가 있습니다.

최대 5 * 104 호출이 addNum 및 findMedian 로 이루어집니다.

후속 조치:

스트림의 모든 정수가 [0, 100] 범위에 있는 경우 솔루션을 최적화하려면 어떻게 해야 합니까?

스트림의 모든 정수 중 99%가 [0, 100] 범위에 있는 경우 솔루션을 어떻게 최적화하시겠습니까?

해결책:

import heapq

class MedianFinder:

    def __init__(self):
        self.left = []
        self.right = []

    def addNum(self, num: int) -> None:
        left = self.left
        right = self.right
        if len(right) == 0:
            heapq.heappush(right, num)
        elif num < right[0]:
            heapq.heappush(left, -num)
        elif num >= right[0]:
            heapq.heappush(right, num)
        if len(left) > len(right) + 1:
            heapq.heappush(right, -heapq.heappop(left))
        if len(right) > len(left) + 1:
            heapq.heappush(left, -heapq.heappop(right))

    def findMedian(self) -> float:
        left = self.left
        right = self.right
        if len(left) == len(right):
            return (right[0] - left[0]) / 2
        if len(left) > len(right):
            return -left[0]
        if len(left) < len(right):
            return right[0]


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