목록Find Median from Data Stream (1)

Scribbling

LeetCode: 295. Find Median from Data Stream

면접 형식의 문제여서 문제를 맞추는 것은 어렵지 않다. 다만 어느정도로 효율적인 알고리즘(시간 및 메모리 측면)을 구현하는지가 관건이다. 가장 간단한 방법은 모든 숫자를 저장하고, 중앙값 search시마다 정렬하는 방법이다. add: O(1) find: O(nlogn) 위의 이유로 비효율적이다. class MedianFinder: def __init__(self): self.arr = [] self.count = 0 def addNum(self, num: int) -> None: self.arr.append(num) self.count += 1 def findMedian(self) -> float: self.arr.sort() if self.count % 2 == 0: return (self.arr[se..
Computer Science/Coding Test 2021. 11. 16. 14:49
이전 Prev 1 Next 다음