程序设计－有一个实时交易系统，成交价格会持续写入。现在需要你设计一个模块，能够：实时接收新的成交价，在任意时刻快速返回当前成交价的中位数
分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程https://www.captainai.net/troubleshooter
import java.util.Collections; import java.util.PriorityQueue; /** * 实时成交价格中位数计算器 * 支持动态插入价格，快速获取当前中位数 * 时间复杂度：插入 O(log n)，查询 O(1) */ public class PriceMedianCalculator { // 最大堆：存储较小的一半元素，堆顶为这部分的最大值 private final PriorityQueue<Double> maxHeap; // 最小堆：存储较大的一半元素，堆顶为这部分的最小值 private final PriorityQueue<Double> minHeap; public PriceMedianCalculator() { // 最大堆：使用反向顺序实现 this.maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 最小堆：默认顺序 this.minHeap = new PriorityQueue<>(); } /** * 添加新的成交价格 * @param price 成交价格 */ public void addPrice(double price) { // 决定将新价格放入哪个堆 if (maxHeap.isEmpty() || price <= maxHeap.peek()) { maxHeap.offer(price); } else { minHeap.offer(price); } // 平衡两个堆的大小 balanceHeaps(); } /** * 平衡两个堆，确保： * 1. maxHeap的大小 >= minHeap的大小 * 2. 两个堆的大小差不超过1 */ private void balanceHeaps() { // maxHeap最多比minHeap多一个元素 if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(maxHeap.poll()); } // 确保maxHeap不会小于minHeap else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(minHeap.poll()); } } /** * 获取当前所有成交价格的中位数 * @return 中位数 * @throws IllegalStateException 如果没有成交价格 */ public double getMedian() { if (maxHeap.isEmpty()) { throw new IllegalStateException("No prices available"); } // 如果总数为奇数，中位数在maxHeap的顶部 if (maxHeap.size() > minHeap.size()) { return maxHeap.peek(); } // 如果总数为偶数，中位数为两个堆顶的平均值 else { return (maxHeap.peek() + minHeap.peek()) / 2.0; } } /** * 获取当前价格总数 */ public int getSize() { return maxHeap.size() + minHeap.size(); } /** * 清空所有价格 */ public void clear() { maxHeap.clear(); minHeap.clear(); } }算法说明
核心思想：使用两个堆（最大堆和最小堆）来维护数据流的中位数
工作原理：
最大堆（maxHeap）存储较小的一半元素，堆顶是这半部分的最大值
最小堆（minHeap）存储较大的一半元素，堆顶是这半部分的最小值
保持两个堆的平衡：
maxHeap.size() == minHeap.size()或maxHeap.size() == minHeap.size() + 1奇数个元素：中位数 = maxHeap的堆顶
偶数个元素：中位数 = (maxHeap堆顶 + minHeap堆顶) / 2
性能优势：
插入操作：O(log n)
查询中位数：O(1)
空间复杂度：O(n)