如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
package jianzhiOffer; import java.util.Comparator; import java.util.PriorityQueue; public class Q25_数据流中的中位数 { class Solution { private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //默认是小顶堆 private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>() { //大顶堆需要反转默认的比较器 @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }); //添加元素num public void Insert(Integer num) { //如果添加之后总元素个数为偶数个,将元素加到小顶堆中 if((maxHeap.size() + minHeap.size() + 1) % 2 == 0) { //如果num的值小于大顶堆中的堆顶元素，将num添加到大顶堆中，并将大顶堆的堆顶元素移入小顶堆 if(maxHeap.size() > 0 && num < maxHeap.peek()) { maxHeap.add(num); minHeap.add(maxHeap.poll()); } else { //否则，直接添加到小顶堆中 minHeap.add(num); } } else { //如果添加之后总元素个数为基数个,将元素加到大顶堆中 //做同样的判断 if(minHeap.size() > 0 && num > minHeap.peek()) { minHeap.add(num); maxHeap.add(minHeap.poll()); } else { maxHeap.add(num); } } } //获得中位数 public Double GetMedian() { if((minHeap.size() + maxHeap.size()) == 0) { return null; } double result; //总个数为偶数个 if((minHeap.size() + maxHeap.size()) % 2 == 0) { result = (minHeap.peek() + maxHeap.peek()) / 2.0; } else { //总数为奇数个 result = maxHeap.peek(); } return result; } } }
