題目描述設計一個數據結構支持兩個操作addNum(num)向數據流中加入一個整數 findMedian()返回當前所有整數的中位數中位數的定義是如果元素個數是奇數中位數是排序后最中間的數。如果元素個數是偶數中位數是排序后中間兩個數的平均值。例如[2,3,4] 的中位數是 3 [2,3] 的中位數是 (2 3) / 2 2.5這道題的難點在于數據是不斷加入的不能每次findMedian()都重新排序。核心思路用兩個堆把所有數分成左右兩半l大頂堆保存較小的一半 r小頂堆保存較大的一半其中l.peek() 左半部分最大值 r.peek() 右半部分最小值這樣中位數就只和兩個堆頂有關如果總數是奇數中位數 l.peek() 如果總數是偶數中位數 (l.peek() r.peek()) / 2.0為什么這樣分如果把所有數字排好序中位數只會出現在中間位置。所以不需要維護完整有序數組只需要維護較小的一半 | 較大的一半左邊最大的數和右邊最小的數正好就是中間附近的兩個數。大頂堆適合快速拿到左半部分最大值小頂堆適合快速拿到右半部分最小值。關鍵不變量整個過程中要始終維護兩個條件1. l 中的數整體 r 中的數 2. l.size() r.size()或者 l.size() r.size() 1也就是說l要么和r一樣多要么只比r多一個。為什么讓l多一個因為這樣元素個數為奇數時可以直接返回l.peek()不用再判斷中位數在哪個堆里。addNum 的過程代碼中有兩個分支。情況一兩個堆大小相同if (l.size() r.size()) { r.offer(num); l.offer(r.poll()); }此時加入新元素后應該讓l比r多一個。操作過程是1. 先把 num 放進 r 2. 再把 r 中最小的數移動到 l這樣可以保證移動到l的數仍然屬于較小的一半。情況二l 比 r 多一個else { l.offer(num); r.offer(l.poll()); }此時加入新元素后應該讓兩個堆重新變成一樣大。操作過程是1. 先把 num 放進 l 2. 再把 l 中最大的數移動到 r這樣可以保證移動到r的數屬于較大的一半。手動模擬以依次加入1, 2, 3, 4, 5為例。這里展示的是邏輯順序不代表 JavaPriorityQueue的真實內部數組順序。初始l [] r []addNum(1)兩個堆大小相同先放入r再把r的最小值移動到ll [1] r []當前中位數1addNum(2)l比r多一個先放入l再把l的最大值移動到rl [1] r [2]當前中位數(1 2) / 2.0 1.5addNum(3)兩個堆大小相同先 r.offer(3)r [2,3] 再 l.offer(r.poll())把 2 放入 l結果l [2,1] r [3]當前中位數2addNum(4)l比r多一個先 l.offer(4)l [4,1,2] 再 r.offer(l.poll())把 4 放入 r結果l [2,1] r [3,4]當前中位數(2 3) / 2.0 2.5addNum(5)兩個堆大小相同先 r.offer(5)r [3,4,5] 再 l.offer(r.poll())把 3 放入 l結果l [3,1,2] r [4,5]當前中位數3所以中位數依次是1, 1.5, 2, 2.5, 3Java 代碼class MedianFinder { PriorityQueueInteger l; PriorityQueueInteger r; public MedianFinder() { l new PriorityQueue((a, b) - b - a); r new PriorityQueue(); } public void addNum(int num) { if (l.size() r.size()) { r.offer(num); l.offer(r.poll()); } else { l.offer(num); r.offer(l.poll()); } } public double findMedian() { if (l.size() r.size()) return l.peek(); return (l.peek() r.peek()) / 2.0; } }PriorityQueue 操作區分這題里最重要的是理解peek()和poll()peek()查看堆頂元素不刪除 poll()取出堆頂元素并刪除 offer()加入一個元素默認的PriorityQueue是小頂堆r new PriorityQueue();所以r.peek() 是 r 中的最小值如果傳入比較器l new PriorityQueue((a, b) - b - a);就可以讓l變成大頂堆l.peek() 是 l 中的最大值易錯點PriorityQueue的隊頭不是最早加入的元素而是優先級最高的元素。默認PriorityQueue是小頂堆不是大頂堆。peek()只是查看堆頂poll()才會刪除堆頂。只維護數量平衡還不夠還要保證l.peek() r.peek()。偶數個數時要寫/ 2.0否則容易寫成整數除法。當前寫法讓l始終不少于r所以奇數時返回的是l.peek()。復雜度分析每次加入一個數時會進行堆的插入和刪除addNumO(log n)查找中位數只需要看堆頂findMedianO(1)兩個堆一共保存所有元素空間復雜度O(n)總結這道題的核心不是排序而是維護中位數兩邊的邊界。用大頂堆l保存較小的一半用小頂堆r保存較大的一半。只要維護好兩個不變量l 中的數整體 r 中的數 l.size() r.size() 或 l.size() r.size() 1中位數就可以通過堆頂快速得到。下次重寫前可以先問自己兩個堆分別保存哪一半l.peek()和r.peek()分別代表什么為什么加入元素時要先放進一個堆再把堆頂移動到另一個堆奇數個元素時為什么可以直接返回l.peek()