目录

三个月算法进阶--day70

2020-11-01 约 108 字预计阅读 1 分钟次阅读

目录

添加元素并保持有序

二分查找

python 堆也是列表

中位数：大顶堆+小顶堆

leetcode剑指offer第41题数据流中的中位数

class MedianFinder:

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

    def addNum(self, num: int) -> None:
        if len(self.max) > len(self.min):
            heapq.heappush(self.min, -heapq.heappushpop(self.max, num))
        else:
            heapq.heappush(self.max, -heapq.heappushpop(self.min, -num))


    def findMedian(self) -> float:
        if len(self.max) == len(self.min):
            return (self.max[0] - self.min[0]) / 2
        else:
            return self.max[0]