295. Find Median from Data Stream

https://leetcode.com/problems/find-median-from-data-stream/

solution

• 双heap

  • 一个最小堆，一个最大堆。数据分成两部分，中位数就是前半部分的最大值，后半部分的最小值

  • 新加入元素，先判断该加入小堆还是大堆，再调整维持平衡

  • 总个数为奇数时，放在哪个堆里可以提前定义好

import heapq

class MedianFinder:
    def __init__(self):
        self.max_heap = []  # 极大堆(python都是极小堆，因此是负数进入). 数据中小的一半进入max_heap
        self.min_heap = []  # 数据中大的一半进入min_heap

    def addNum(self, num: int) -> None:
        if not self.max_heap or num <= -self.max_heap[0]:  # -max_heap[0] 是小数据中的最大值
            # 多一个的奇数的话，进入max_heap. findMedian奇数的话就从max_heap中取
            heapq.heappush(self.max_heap, -num)
            if len(self.max_heap) - len(self.min_heap) > 1:
                heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        else:
            heapq.heappush(self.min_heap, num)
            if len(self.max_heap) < len(self.min_heap):
                heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

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

时间复杂度：O(nlog(n)) 空间复杂度：O(n)

• SortedDict

时间复杂度：O() 空间复杂度：O()

• 二分法

  • 使用二分法插入，使得数据流是有序的

follow up

480. Sliding Window Median