【python-leetcode295-双堆】数据流的中位数

发布时间：2020-12-20 09:54:16 所属栏目：Python 来源：网络整理

导读：中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。例如， [2,3,4]?的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构： void addNum(int num) - 从数据流中添加一个整数到数据结构中。 do

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

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

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

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

需要明确的是：大顶堆中的元素是小顶堆里最小值取负后再加入的，因此大顶堆中（忽略负号）的元素肯定比小顶堆中的小。然后，让小顶堆的长度总是大于或等于大顶堆。因此当长度为奇数时，中位数就是小顶堆的堆首，为偶数时就是（大顶堆堆首+小顶堆堆首）/2

import heapq
class MedianFinder(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.len = 0
        #小顶堆
        self.minheap = []
        大顶堆
        self.maxheap = []

    def addNum(self,num):
        
        :type num: int
        :rtype: None
        """
        加入一个数，长度加1
        self.len += 1
        首先明确的是python中的heapq是小顶堆
        heappushpop：将num放入堆中，然后弹出并返回heap的最小元素。
        heappush：将item的值加入heap中，保持堆的不变性。
        heappop：弹出并返回heap的最小的元素，保持堆的不变性。
        heapq.heappush(self.maxheap,-heapq.heappushpop(self.minheap,num))
        if len(self.maxheap) > len(self.minheap):
            heapq.heappush(self.minheap,-heapq.heappop(self.maxheap))
        print("小顶堆：",self.minheap)
        大顶堆： findMedian(self):
        
        :rtype: float
        if self.len & 1 == 0:
            return (self.minheap[0] - self.maxheap[0]) / 2.0
        return self.minheap[0]
        

m=MedianFinder()
m.addNum(4)
中位数：57",m.findMedian())

过程：负号只是占位用。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!