class MedianFinder:
def __init__(self):
self.small = [] # max heap
self.large = [] # min heap
# tc O(lgN) sc O(N)
def addNum(self, num: int) -> None: # keep self.small size of k
if len(self.small) == len(self.large):
heapq.heappush(self.large,-heapq.heappushpop(self.small, -num))
else:
heapq.heappush(self.small, -heapq.heappushpop(self.large, num))
# tc O(1) sc O(1)
def findMedian(self) -> float:
if len(self.small) == len(self.large):
return (-self.small[0]+self.large[0])/2
else:
return self.large[0]
Follow up
If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
class MedianFinder:
def __init__(self):
self.bucket = [0]*101
self.total = 0
# tc O(1) sc O(1)
def addNum(self, num: int) -> None: # keep self.small size of k
self.bucket[num] += 1
self.total += 1
# tc O(1) sc O(1)
def findMedian(self) -> float:
cnt = x = 0
while cnt < self.total//2 :
cnt += self.bucket[x]
x += 1
fst = x -1
snd = fst
while cnt < self.total//2 +1 :
snd += 1
cnt += self.bucket[snd]
snd = snd -1 if snd != fst else snd
if self.total % 2 == 0:
return fst
return fst/2 + snd/2
If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
class MedianFinder:
def __init__(self):
self.bucket = [0]*101
self.total = 0
self.below_zero = 0
# tc O(1) sc O(1)
def addNum(self, num: int) -> None: # keep self.small size of k
if num < 0:
self.below_zero += 1
elif num > 100 : continue
self.bucket[num] += 1
self.total += 1
# tc O(1) sc O(1)
def findMedian(self) -> float:
cnt = self.below_zero
x = 0
while cnt < self.total//2 :
cnt += self.bucket[x]
x += 1
fst = x -1
snd = fst
while cnt < self.total//2 +1 :
snd += 1
cnt += self.bucket[snd]
snd = snd -1 if snd != fst else snd snd = snd -1 if snd != fst else snd
if self.total % 2 == 0:
return fst
return fst/2 + snd/2