295. Find Median from Data Strea

295. Find Median from Data Stream

class MedianFinder(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.low = []
        self.high = []

    def addNum(self, num):
        """
        :type num: int
        :rtype: None
        """
        if len(self.low) == len(self.high):
            if len(self.low) == 0 or num < -self.low[0]:
                heapq.heappush(self.low, -num)
            else:
                heapq.heappush(self.high, num)
        elif len(self.low) > len(self.high):
            if num > -self.low[0]:
                heapq.heappush(self.high, num)
            else:
                temp = -self.low[0]
                heapq.heappop(self.low)
                heapq.heappush(self.low, -num)
                heapq.heappush(self.high, temp)
        else:
            if num > self.high[0]:
                temp = self.high[0]
                heapq.heappop(self.high)
                heapq.heappush(self.low, -temp)
                heapq.heappush(self.high, num)
            else:
                heapq.heappush(self.low, -num)

    def findMedian(self):
        """
        :rtype: float
        """
        if len(self.low) == len(self.high):
            return 0.5 * (self.high[0] - self.low[0])
        elif len(self.low) > len(self.high):
            return -self.low[0]
        else:
            return self.high[0]