一、题目
1、审题
2、分析
实现一个数据结构，可以添加整形元素，并可以返回排序后的中位数。
二、解答
1、思路
采用两个 PriorityQueue。
①、采用两个 PriorityQueue，PriorityQueue 具有对元素进行自动排序的功能。
②、一个为 maxQueue，记录比中位数大的所有元素，另一个为 smallQueue， 记录比中位数小的元素。
③、为了方便统计数中位数，smallQueue 中存储的元素为其负值，这样，候补中位数就在 smallQueue 的队头。
④、若元素总数为奇数，直接返回 largeQueue 的队头，若元素为偶数，返回 largeQueue 的队头和 smallQueue 队头的负值，两元素的平均。
public class MedianFinder { /** initialize your data structure here. */ private Queue<Long> small = new PriorityQueue<Long>(); private Queue<Long> large = new PriorityQueue<>(); public void addNum(int num) { large.add((long) num); small.add(-large.poll()); if(large.size() < small.size()) large.add(-small.poll()); } public double findMedian() { if(large.size() > small.size()) return large.peek(); return (large.peek() - small.peek()) / 2.0; } }
295. Find Median from Data Stream
原文：https://www.cnblogs.com/skillking/p/10016084.html