中位数
数据流中的中位数
http://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1
// 大顶端：最大的元素在第一个 PriorityQueue<Integer> heapBig = new PriorityQueue<>(Comparator.reverseOrder()); // 把comparable取反// 小顶堆：自然序，最小的元素在第一个 PriorityQueue<Integer> heapSmall = new PriorityQueue<>();
public void Insert(Integer num) { count++; heapBig.add(num); if (heapBig.size() > heapSmall.size() + 1) { heapSmall.add(heapBig.peek()); heapBig.poll(); } // 保证左右两个堆的size最多差1 if (!heapSmall.isEmpty() && heapBig.peek() > heapSmall.peek()) { heapSmall.add(heapBig.peek()); heapBig.poll(); } // 如果左边的最大值大于了右边的最小值，则移入右边 if (heapSmall.size() > heapBig.size()) { heapBig.add(heapSmall.peek()); heapSmall.poll(); } // 如果右边的size大于左边，则移入左边，因为左边第一个为中位数 }
分享一个插入的思路：
前提：设置一个大顶堆一个小顶堆，大顶堆中的顶部保存了中位数，大顶堆中其余元素都是排序后的中位数左边的元素；小顶堆中的元素都是大于中位数的元素；
在插入的时候要满足以下三个条件：
1. 大小顶堆size之差<=1;
2. 大顶堆的size>=小顶堆的size；
3. 大顶堆中的元素都小于小顶堆中的元素；
这样，大顶堆的第一个元素或者大顶堆第一个元素和小顶堆第一个元素的avg就是中位数啦。
查看12道真题和解析
