Clear Python solution with readability over "concise"-ness


  • 0
    M
    from heapq import *
    
    class MaxHeap(object):
        
        def __init__(self):
            self.heap = []
            
        def __len__(self):
            return len(self.heap)
            
        def push(self, num):
            heappush(self.heap, -num)
            
        def pop(self):
            return -heappop(self.heap)
            
        def pushpop(self, num):
            return -heappushpop(self.heap, -num)
            
        def getMax(self):
            return -self.heap[0]
            
    
    class MinHeap(object):
        
        def __init__(self):
            self.heap = []
            
        def __len__(self):
            return len(self.heap)
            
        def push(self, num):
            heappush(self.heap, num)
            
        def pop(self):
            return heappop(self.heap)
            
        def pushpop(self, num):
            return heappushpop(self.heap, num)
            
        def getMin(self):
            return self.heap[0]
        
    
    class MedianFinder(object):
    
        def __init__(self):
            """
            initialize your data structure here.
            """
            # Constaints: 
            # - Minheap must only store elements > median.
            # - Maxheap must only store elements < median.
            # - len(maxheap) >= len(minheap), but lengths must differ by at most one.
            
            self.minheap = MinHeap()
            self.maxheap = MaxHeap() 
    
        def addNum(self, num):
            """
            :type num: int
            :rtype: void
            """
            # Must maintain the constraint that len(maxheap) >= len(minheap) by at most one element throughout.
            if len(self.maxheap) == len(self.minheap):
                # Add num to maxheap, then re-balance both heaps to maintain all constraints.
                self.minheap.push(self.maxheap.pushpop(num))
                self.maxheap.push(self.minheap.pop())
            else:
                # Must be the case that len(maxheap) = len(minheap) + 1, so add num to minheap, and re-balance heaps to maintain all constraints.
                self.maxheap.push(self.minheap.pushpop(num))
                self.minheap.push(self.maxheap.pop())
    
        def findMedian(self):
            """
            :rtype: float
            """
            if len(self.minheap) == len(self.maxheap):
                return float(self.maxheap.getMax() + self.minheap.getMin()) / 2
            else:
                return float(self.maxheap.getMax())
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.