[LeetCode][Python3] 295. Find Median from Data Stream

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]