Skip to main content

Find Median from Data Stream

Question​

com

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)

Solution​

all//Find Median from Data Stream.py


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