黃金挑戰(zhàn)-數(shù)據(jù)流的中位數(shù)

1.數(shù)據(jù)流中中位數(shù)的問題

LeetCode295
https://leetcode.cn/problems/find-median-from-data-stream/

思路分析

中位數(shù)的問題，我們一般都可以用 大頂堆+小頂堆 來求解

小頂堆（minHeap）：存儲所有元素中較大的一半，堆頂元素是其中最小的數(shù)
大頂堆（maxHeap）：存儲所有元素中較小的一半，堆頂元素是其中最大的數(shù)

相當于，把所有元素分成了大和小兩半，計算中位數(shù)，只需要大的那半的最小值和小的那半的最大值即可。

如[1,2,3,4,5]，分成小頂堆[3,4,5]，大頂堆[2,1]，中位數(shù)為3

過程
加1 小頂堆[1] 大頂堆[] 中位數(shù) 1
加2 小頂堆[2] 大頂堆[1] 中位數(shù) (2+1)/2
加3 小頂堆[2,3] 大頂堆[1] 中位數(shù) 3
加4 小頂堆[3,4] 大頂堆[2,1] 中位數(shù) (3+2)/2
加5 小頂堆[3,4,5] 大頂堆[2,1] 中位數(shù) 3

代碼實現(xiàn)

Java中的堆（即優(yōu)先隊列）可方便實現(xiàn)，c++、python里沒有提供堆結(jié)構(gòu)，需要自己構(gòu)造

class MedianFinder {// 小頂堆中存儲的是比較大的元素，堆頂是其中的最小值PriorityQueue<Integer> minHeap;// 大頂堆中存儲的是比較小的元素，堆頂是中期的最大值PriorityQueue<Integer> maxHeap;public MedianFinder() {this.minHeap = new PriorityQueue<>();this.maxHeap = new PriorityQueue<>((a, b) -> b - a);}public void addNum(int num) {// 小頂堆存儲的是比較大的元素，num大于小頂堆中根元素時進入minHeapif (minHeap.isEmpty() || num > minHeap.peek()){minHeap.offer(num);// 如果minHeap比maxHeap多2個元素，就平衡一下if (minHeap.size() - maxHeap.size() > 1){maxHeap.offer(minHeap.poll());}}else{maxHeap.offer(num);// 這樣可以保證多的那個元素肯定在minHeapif(maxHeap.size() - minHeap.size() > 0){minHeap.offer(maxHeap.poll());}}}public double findMedian() {if(minHeap.size() > maxHeap.size()){return minHeap.peek();}else if(minHeap.size() < maxHeap.size()){return maxHeap.peek();}else{return (minHeap.peek() + maxHeap.peek())/2.0;}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/