data stream

295. Find Median from Data Stream.py

class MedianFinder:
    """
    Binary Search + Insert
    T: O(logn) +O(n) = O(n) for add function O(1) for findMedian.
    S: O(n)
    我們用一個array不斷存放新進來的data, as time goes, it's become inefficient in terms of space(not scalable)
    
    Two heaps: max heap+min_heap+balance
    T: 3*O(logn) for add function O(1) for findMedian.
    S: O(n)
    
    Follow-up:
    
        1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?

        We can maintain an integer array of length 100 to store the count of each number along with a total count. Then, we can iterate over the array to find the middle value to get our median.
        
        count array
        min
         0 1 2 3 4.  max
        [0,1,3,0,0,0,5]
        count[ele] = freq
        index is element, value corresponding to index is frequency
    如果我們已知數據會在一定range分佈可以想到count array
    
    total_count
    for i in range(min, max):
        
    """
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.nums = []
        

    def addNum(self, num: int) -> None:
        n = len(self.nums)
        if n == 0:
            self.nums.append(num)
            return
        ix = bisect.bisect_left(self.nums, num) # O(logn)
        self.nums.insert(ix, num) #O(n)
        return

    def findMedian(self) -> float:
        n = len(self.nums)
        if n % 2 == 0:
            return (self.nums[n//2-1]+self.nums[n//2]) / 2.0
        else:
            return self.nums[n//2]

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.max_heap = [] # [1]
        self.min_heap = [] # [2,3]
        

    def addNum(self, num: int) -> None:
        if not self.max_heap or num < -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)
        # balance
        if len(self.min_heap) > len(self.max_heap):
            val = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -val)
        if len(self.max_heap) > len(self.min_heap)+1:
            val = heapq.heappop(self.max_heap)
            heapq.heappush(self.min_heap, -val)
        return

    def findMedian(self) -> float:
        n = len(self.max_heap)+len(self.min_heap)
        if n % 2 == 0:
            return (-self.max_heap[0]+self.min_heap[0]) / 2.0
        else:
            return -self.max_heap[0]

class MedianFinder:
    """
     0 1 2 3 4    100
    [0,1,2,1,0,....,0]
    
    1 
       m
    2 
       m
    3 
         m
    4
         m
    
    """
    def __init__(self, min_range=0, max_range=100):
        self.count = [0 for i in range(min_range, max_range+1)]
        self.total_count = 0
        
    def addNum(self, num: int) -> None:
        self.count[num] += 1
        self.total_count += 1
        
    def findMedian(self) -> float:
        if self.total_count == 1:
            middle = 1
        elif self.total_count % 2 == 0:
            middle = self.total_count // 2
        else:
            middle = self.total_count // 2+1
        c = 0
        for i, freq in enumerate(self.count):
            c+=freq
            if c == middle:
                if self.total_count % 2 == 0:
                    # O(n)
                    next_non_zero = i+1
                    while not self.count[next_non_zero]:
                        next_non_zero +=1
                    return (i+next_non_zero) / 2.0
                else:
                    return i
            elif c > middle:
                return i
                
            
    
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()