题解 | #售价的中位数#

• 题目考察的知识点 : 大小堆
• 题目解答方法的文字分析：

1. 使用两个优先队列 l 和 r 分别存储小于等于中位数的元素和大于中位数的元素；
2. 每当新加入一个元素时，先将其加入 l  中，然后根据当前堆内元素情况，调整两个堆顶元素，使得两个堆的大小尽量平衡；
3. 根据当前堆的大小，计算出当前的中位数，将其加入结果数组中。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param prices int整型一维数组
# @return double浮点型一维数组
#
import heapq
class Solution:
    def findMedianPrice(self, prices: List[int]) -> List[float]:
        res = []
        # 左右两个堆，左边的堆存放小于等于中位数的元素，右边的堆存放大于中位数的元素
        r = []
        l = []
        n = len(prices)

        for i in range(n):
            # 将元素加入左边堆
            heapq.heappush(l, -prices[i])
            # 如果右边堆不为空且左边堆的堆顶元素比右边堆的堆顶元素大，则交换两个堆顶元素
            if r and -l[0] > r[0]:
                t1 = -heapq.heappop(l)
                t2 = heapq.heappop(r)
                heapq.heappush(l, -t2)
                heapq.heappush(r, t1)
            # 如果左边堆的大小比右边堆的大小大 2，则将左边堆的堆顶元素取出并加入右边堆
            if len(l) - len(r) == 2:
                heapq.heappush(r, -heapq.heappop(l))
            # 根据当前堆的大小计算出当前的中位数，并将其加入结果数组中
            if i % 2 == 1:
                res.append(0.5 * (-l[0] + r[0]))
            else:
                res.append(-l[0])

        return res