題目鏈接

295.數據流的中位數

class MedianFinder {PriorityQueue<Integer> left;//隊頭最大PriorityQueue<Integer> right;//隊頭最小public MedianFinder() {left = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});right = new PriorityQueue<>();}public void addNum(int num) {if (left.size() <= right.size()) {left.offer(num);} else {right.offer(num);}if (!left.isEmpty() && !right.isEmpty() && left.peek() > right.peek()) {left.offer(right.poll());right.offer(left.poll());}}public double findMedian() {if (left.size() > right.size()) {return left.peek();} else {return (left.peek() + right.peek()) / 2.0;}}
}

小結：兩個優先級隊列，左隊列最大值不超過右隊列最小值，且左隊列容量=右隊列(偶數)或左隊列容量=右隊列+1(奇數)，這樣就可以根據兩個隊列的隊頭元素直接計算出中位數。