1.题目基本信息

1.1.题目描述

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。

• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。

• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

1.2.题目地址

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

2.解题方法

2.1.解题思路

双顶堆

使用左大顶堆leftMaxHeap维护左半部分的小值，右小顶堆rightMinHeap维护右半部分的大值；在增加的元素的时候根据两堆的顶部元素进行调整，并将值插入到合适的堆中

3.解题代码

python代码

import heapq

class MedianFinder:
    # 思路：对顶堆。使用左大顶堆leftMaxHeap维护左半部分的小值，右小顶堆rightMinHeap维护右半部分的大值；在增加的元素的时候根据两堆的顶部元素进行调整，并将值插入到合适的堆中
    def __init__(self):
        self.leftMaxHeap = []  # 最大堆
        self.rightMinHeap = []

    def addNum(self, num: int) -> None:
        if len(self.leftMaxHeap) == len(self.rightMinHeap):
            tmp = self.rightMinHeap[0] if len(self.rightMinHeap) > 0 else inf
            if num > tmp:
                heapq.heappush(self.leftMaxHeap, -heapq.heappop(self.rightMinHeap))
                heapq.heappush(self.rightMinHeap, num)
            else:
                heapq.heappush(self.leftMaxHeap, -num)
        else:   # len(self.leftMaxHeap)==len(self.rightMinHeap)+1
            tmp = -self.leftMaxHeap[0] if len(self.leftMaxHeap) > 0 else -inf
            if num < tmp:
                heapq.heappush(self.rightMinHeap, -heapq.heappop(self.leftMaxHeap))
                heapq.heappush(self.leftMaxHeap, -num)
            else:
                heapq.heappush(self.rightMinHeap, num)

    def findMedian(self) -> float:
        # print("t1", self.leftMaxHeap)
        # print("t2", self.rightMinHeap)
        result = -self.leftMaxHeap[0] if len(self.leftMaxHeap) != len(self.rightMinHeap) else (-self.leftMaxHeap[0] + self.rightMinHeap[0]) / 2
        # print("t3", result)
        return result

4.执行结果