Problem :

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


My Solution :

class MedianFinder:

def __init__(self):
self.nums = []

def addNum(self, num: int) -> None:
idx = self.bin_search(self.nums, num)
self.nums.insert(idx, num)

def findMedian(self) -> float:
size = len(self.nums)
if size % 2 == 0:
return (self.nums[(size-1)//2] + self.nums[size//2]) / 2
return self.nums[size//2]

def bin_search(self, arr, x):
lo, high = 0, len(arr)
while lo < high:
mid = (lo + high) // 2
if arr[mid] > x:
high = mid
else:
lo = mid + 1
return high


Comment :

입력이 들어올 때 마다 binary search로 삽입될 index를 찾아서 삽입한다. 정렬된 list에서는 중위 값을 바로 리턴할 수 있다. 아래는 파이썬 표준 라이브러리 bisect.insort 를 활용한 버전.


My Solution 2 :

from bisect import insort


class MedianFinder:

def __init__(self):
self.nums = []

def addNum(self, num: int) -> None:
insort(self.nums, num)

def findMedian(self) -> float:
size = len(self.nums)
if size % 2 == 0:
return (self.nums[(size-1)//2] + self.nums[size//2]) / 2
return self.nums[size//2]