题解 | #售价的中位数#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param prices int整型一维数组
     * @return double浮点型一维数组
     */
    public double[] findMedianPrice (int[] prices) {
        // write code here
        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;
    }
}

该段代码使用的编程语言是Java。

这段代码是一个解决中位数价格问题的解决方案。给定一个整型向量prices，函数findMedianPrice会返回一个浮点型向量，其中包含了每次插入价格后的中位数。该问题通过维护两个堆来解决，一个最大堆l和一个最小堆r。