295. Find Median from Data Stream
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
For example,
[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
- void addNum(int num) - Add a integer number from the data stream to the data structure.
- double findMedian() - Return the median of all elements so far.
My Answer 1: Output Limit Exceeded (14 / 18 test cases passed.)
import numpy as np
class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.numlist = []
def addNum(self, num: int) -> None:
if num >= 0:
for i in range(len(self.numlist)):
if num <= self.numlist[i]:
self.numlist.insert(i, num)
return
# num 이 젤 크면 맨 뒤에 append
self.numlist.append(num)
else:
for i in range(len(self.numlist)):
if num >= self.numlist[i]:
self.numlist.insert(i, num)
return
# num 이 젤 크면 맨 뒤에 append
self.numlist.append(num)
def findMedian(self) -> float:
print(self.numlist)
nplist = np.array(self.numlist)
return np.median(nplist)
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()리스트를 사용
addNum 에서는 정렬한 상태로 리스트를 유지하기 위해서 num 을 양수/음수로 나눠서 각자 자리에 위치하도록 함
findMedian 에서는 맨 처음 값과 마지막 값을 2로 나눈 값을 리턴하도록 하려 했는데 뭔가 이상해서
파이썬의 numpy 라이브러리를 이용해서 Median 값을 구해줬다
근데도.. Output Limit Exceeded 라는 점~
2 HEAPS
Solution 1: Runtime: 252 ms - 33.27% / Memory Usage: 25.8 MB - 26.32%
"""
## RC ##
## APPROACH : 2 HEAPS ##
## LOGIC ##
## One minheap to store low values and second maxheap to store max values, we keep track and update median every time after insertion ##
## TIME COMPLEXITY : O(logN) ##
## SPACE COMPLEXITY : O(N) ##
## EXAMPLE ##
Adding number 41
MaxHeap lo: [41] // MaxHeap stores the largest value at the top (index 0)
MinHeap hi: [] // MinHeap stores the smallest value at the top (index 0)
Median is 41
=======================
Adding number 35
MaxHeap lo: [35] // max heap stores smaller half of nums
MinHeap hi: [41] // min heap stores bigger half of nums
Median is 38
=======================
Adding number 62
MaxHeap lo: [41, 35]
MinHeap hi: [62]
Median is 41
=======================
Adding number 4
MaxHeap lo: [35, 4]
MinHeap hi: [41, 62]
Median is 38
=======================
Adding number 97
MaxHeap lo: [41, 35, 4]
MinHeap hi: [62, 97]
Median is 41
=======================
Adding number 108
MaxHeap lo: [41, 35, 4]
MinHeap hi: [62, 97, 108]
Median is 51.5
"""
class MedianFinder:
def __init__(self):
self.lo = []
self.hi = []
def addNum(self, num):
heappush(self.lo, -num) # lo is maxheap, so -1 * num
heappush(self.hi, -self.lo[0]) # hi is minheap
heappop(self.lo)
if len(self.lo) < len(self.hi):
heappush(self.lo, -self.hi[0])
heappop(self.hi)
def findMedian(self):
if len(self.lo) > len(self.hi):
return -self.lo[0]
else:
return (self.hi[0] - self.lo[0]) / 2 # - as low has -ve values저는 min-heap, max-heap 그지입니다..
min-heap: 부모노드의 값이 자식노드의 값보다 작다.
max-heap: 부모노드의 값이 자식노드의 값보다 크다.
트리의 형태인데.. 흠
일단 여기서는 MinHeap 은 Median 값보다 큰 값들이,
MaxHeap 은 Median 값보다 작은 값들이 들어가는 것 같다.
배열에 있는 모든 수의 개수가 홀수인 경우 최대 힙의 가장 위(앞)에 있는 수를 반환한다.
짝수인 경우 최대힙, 최소힙의 가장 위(앞)에 있는 수의 평균을 구해서 반환한다.
heappush 를 하게 되면 min heap 구조로 push 됨 | heappop 은 맨 앞 원소를 pop
__init__
lo (maxheap), hi (minheap) 리스트 생성
addNum
lo 에다가 -num 값을 넣어주고 맨 앞에 값을 hi 로 보냄 (hi 에 push 후 lo 에서는 pop)
lo 길이가 hi 보다 작으면 hi 의 맨 앞 값을 lo 로 보내서 길이를 맞춰준다
findMedian
lo 와 hi 의 길이 차이가 나면 홀수이므로 lo 의 맨 앞 값을 리턴
길이가 같으면 짝수이므로 hi 와 lo 의 맨 앞 값의 차이 / 2 를 리턴
lo 가 MaxHeap lo: [41, 35, 4] 이런식으로 거꾸로 정렬되어야 하니까 - (마이너스)를 붙여준듯
