[LeetCode][Python3] 295. Find Median from Data Stream
2019. 4. 2. 01:02 |
프로그래밍/LeetCode
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]
'프로그래밍 > LeetCode' 카테고리의 다른 글
| [LeetCode][Python3] 210. Course Schedule II (0) | 2019.04.05 |
|---|---|
| [LeetCode][Python3] 148. Sort List (1) | 2019.04.04 |
| [LeetCode][Python3] 139. Word Break (0) | 2019.04.03 |
| [LeetCode][Python3] 56. Merge Intervals (0) | 2019.04.03 |
| [LeetCode][Python3] 236. Lowest Common Ancestor of a Binary Tree (0) | 2019.04.01 |
| [LeetCode][Python3] 207. Course Schedule (0) | 2019.03.31 |
| [LeetCode][Python3] 116. Populating Next Right Pointers in Each Node (0) | 2019.03.30 |
| [LeetCode][Python3] 208. Implement Trie (Prefix Tree) (1) | 2019.03.30 |
최근에 달린 댓글 최근에 달린 댓글