You are viewing a single comment's thread. Return to all comments →
Python Interview appropriate heap solution addNum: O(log N) findMedian: O(1) Total = O (log N)
from heapq import heappush, heappop class Median: def __init__(self): self.maxHeap, self.minHeap = [], [] def addNum(self, num): heappush(self.maxHeap, -num) if self.minHeap and self.maxHeap and -self.maxHeap[0] > self.minHeap[0]: heappush(self.minHeap, -heappop(self.maxHeap)) if len(self.minHeap) > len(self.maxHeap) + 1: heappush(self.maxHeap, -heappop(self.minHeap)) if len(self.maxHeap) > len(self.minHeap) + 1: heappush(self.minHeap, -heappop(self.maxHeap)) def findMedian(self): if len(self.maxHeap) > len(self.minHeap): return float(-self.maxHeap[0]) if len(self.maxHeap) < len(self.minHeap): return float(self.minHeap[0]) else: return (self.minHeap[0] - self.maxHeap[0]) / 2 def runningMedian(a): obj = Median() result = list() for i in a: obj.addNum(i) result.append(obj.findMedian()) return result
Seems like cookies are disabled on this browser, please enable them to open this website
Find the Running Median
You are viewing a single comment's thread. Return to all comments →
Python Interview appropriate heap solution addNum: O(log N) findMedian: O(1) Total = O (log N)