剑指offer-python:38.数据流中的中位数

剑指offer-python:38.数据流中的中位数,第1张

剑指offer-python:38.数据流中的中位数

题目:如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

例如,

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

思路:使用两个堆,最大堆存储较小的数据,最小堆存储较大的数据。添加数字时,先添加到最大堆,然后最大堆返回一个最大的数字给最小堆,最后为了平衡,可能需要最小堆还给最大堆一个最小值,以保证最大堆的长度>=最小堆的长度。由于headpq是最小堆,所以使用取反实现最大堆。添加数字:Time-O(logn),取出中位数:Time-O(1)。

调用heapq库。

代码:

import heapq as hq

class MedianFinder:
    def __init__(self):
        self.lo , self.hi = [] , []

    def addN(self , num):
        hq.heappush(self.lo , -num)
        hq.heappush(self.hi , -hq.heappop(self.lo))

        print('lo = {} , hi = {}'.format(self.lo , self.hi))

        if len(self.lo) < len(self.hi):
            hq.heappush(self.lo , -hq.heappop(self.hi))

    def findMedian(self ):
        if len(self.lo) == len(self.hi):
            return (-self.lo[0] + self.hi[0]) / 2.0
        else:
            return float(-self.lo[0])

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5721099.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-18

发表评论

登录后才能评论

评论列表(0条)

保存