Skip to main content

Find Median from Data Stream



How can I efficiently find the median of a data stream with a given set of numbers?

Example 1
Input: [2,1,5,7,2,0,5]

Output: 3 (median is 3, which is the average of the two middle elements: 2 and 5)


all//Find Median from Data

import heapq

class MedianFinder:
def __init__(self):
initialize your data structure here.
self.heaps = [], []

def addNum(self, num):
:type num: int
:rtype: void
small, large = self.heaps
heapq.heappush(small, -heapq.heappushpop(large, num))
if len(large) < len(small):
heapq.heappush(large, -heapq.heappop(small))

def findMedian(self):
:rtype: float
small, large = self.heaps
if len(large) > len(small):
return float(large[0])
return (large[0] - small[0]) / 2.0