【leetcode hot 100 295】数据流的中位数

解法一：申请两个堆。一个堆存放比中位数小的数，是大根堆；一个堆存放比中位数大的数，是小根堆。

class MedianFinder {PriorityQueue<Integer> queMin; // 存放比中位数小的数->大根堆PriorityQueue<Integer> queMax; // 存放比中位数大的数->小根堆public MedianFinder() {queMin = new PriorityQueue<Integer>((a, b) -> (b - a));queMax = new PriorityQueue<Integer>((a, b) -> (a - b));}public void addNum(int num) {if (queMin.isEmpty() || num <= queMin.peek()) {  // 要=，要保证都是先加queMinqueMin.offer(num);if (queMin.size() > queMax.size()+1) {  // +1 要在Max上queMax.offer(queMin.poll());}} else {queMax.offer(num);if (queMax.size() > queMin.size()) {  // 没有+1了，要保证都是先加queMinqueMin.offer(queMax.poll());}}}public double findMedian() {if (queMin.size() > queMax.size()) {return queMin.peek(); // 因为都是先加queMin}return (queMin.peek() + queMax.peek()) / 2.0; // 注意除2.0 才能返回小数点}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

注意：

• 在加入元素过程中，要持续保持先加queMin：num <= queMin.peek() 有等号；queMin.size() > queMax.size()+1 +1 要在Max上；queMax.size() > queMin.size() 没有+1了。
• 因此为奇数时（大小根堆数目不同），先返回queMin的。
• return (queMin.peek() + queMax.peek()) / 2.0 这里要除2.0 才能返回小数点