Python栈的应用：数据流中的中位数

2023-04-11 00:00:00 python 中位数数据流

题目描述：

如何得到一个数据流中的中位数？如果数据流中的数字个数是偶数，则中位数是所有位于中间两个数字的平均值，如果数据流中的数字个数是奇数，则中位数是所有位于中间的数字。

解题思路：

可以维护两个栈，一个最小栈放较大的数，一个最大栈放较小的数，这样可以保证最小栈的数比最大栈的数大，且两个栈数的个数之差不超过1。当需要更新中位数时，如果两个栈的数的个数相等，中位数为两个栈的栈顶取平均数；否则中位数为数的个数更多的栈的栈顶。

代码演示：

class MedianFinder:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.small = []  # 最大栈
        self.large = []  # 最小栈

    def addNum(self, num: int) -> None:
        """
        向数据流中添加一个整数
        """
        if len(self.small) == len(self.large):
            # 加入最小栈
            heapq.heappush(self.large, -heapq.heappushpop(self.small, -num))
        else:
            # 加入最大栈
            heapq.heappush(self.small, -heapq.heappushpop(self.large, num))

    def findMedian(self) -> float:
        """
        返回数据流中的中位数
        """
        if len(self.small) == len(self.large):
            # 两个栈的长度相等，取两个栈顶元素的平均值
            return (-self.small[0] + self.large[0]) / 2
        else:
            # 数的个数更多的栈的栈顶
            return self.large[0]

测试：

finder = MedianFinder()
for num in [1, 2, 3, 4, 5]:
    finder.addNum(num)
    print(finder.findMedian())  # 1，1.5，2，2.5，3

以上就是 Python 栈的应用：数据流中的中位数的详细解读和代码演示。

相关文章