We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This follows Gayle Laakmann McDowell's approach published by HackerRank (see here) but in Python 3:
importheapqdefaddNum(num,lowers,highers):ifnotlowersornum<-lowers[0]:heapq.heappush(lowers,-num)else:heapq.heappush(highers,num)defrebalance(lowers,highers):iflen(lowers)-len(highers)>=2:heapq.heappush(highers,-heapq.heappop(lowers))eliflen(highers)-len(lowers)>=2:heapq.heappush(lowers,-heapq.heappop(highers))defgetMedian(lowers,highers):iflen(lowers)==len(highers):return(-lowers[0]+highers[0])/2iflen(lowers)>len(highers):returnfloat(-lowers[0])else:returnfloat(highers[0])defrunningMedian(a):lowers=[]# max heap, vals should go in and come out negatedhighers=[]# min heap, vals should go in positiveresult=[]forvina:addNum(v,lowers,highers)rebalance(lowers,highers)result.append(round(getMedian(lowers,highers),1))returnresult
Unfortunately, the heapq module is not object-oriented, only implements a min-heap discipline, and does not provide the ability to use a custom comparator, which would make this way easier with regard to the max-heap.
Cookie support is required to access HackerRank
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 →
This follows Gayle Laakmann McDowell's approach published by HackerRank (see here) but in Python 3:
Unfortunately, the heapq module is not object-oriented, only implements a min-heap discipline, and does not provide the ability to use a custom comparator, which would make this way easier with regard to the max-heap.