题解 | #售价的中位数#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param prices int整型一维数组
     * @return double浮点型一维数组
     */
    public double[] findMedianPrice (int[] prices) {
        List<Double> res = new ArrayList<>();
        PriorityQueue<Integer> r = new PriorityQueue<>();
        PriorityQueue<Integer> l = new PriorityQueue<>((a, b) -> b - a);
        int n = prices.length;
        for (int i = 0; i < n; i++) {
            l.add(prices[i]);
            if (!r.isEmpty() && l.peek() > r.peek()) {
                int t1 = l.poll();
                int t2 = r.poll();
                l.add(t2);
                r.add(t1);
            }
            if (l.size() - r.size() == 2) {
                r.add(l.poll());
            }
            if ((i & 1) == 1) {
                res.add(0.5 * (l.peek() + r.peek()));
            } else {
                res.add(1.0 * l.peek());
            }
        }

        double[] result = new double[res.size()];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
}

一、题目考察的知识点

对顶堆

二、题目解答方法的文字分析

1. 创建一个空的浮点型向量res，用于存储每次操作后的中位数。
2. 创建一个最小堆r和一个最大堆l。
3. 遍历输入的价格数组prices，对于每个价格：将价格添加到最大堆l中。如果最小堆r不为空且最大堆l的堆顶元素大于最小堆r的堆顶元素，则交换两个堆顶元素。如果最大堆l的大小比最小堆r的大小多2个，则将最大堆l的堆顶元素弹出并添加到最小堆r中。如果当前操作是奇数次操作（根据索引判断），将最大堆l的堆顶元素作为中位数，将其添加到结果向量res中。如果当前操作是偶数次操作，取最大堆l和最小堆r的堆顶元素的平均值作为中位数，并添加到结果向量res中。
4. 将结果向量res转换为浮点型数组并返回。

三、解题语言：Java