0295. 數據流的中位數 · ttttt

# 0295. 數據流的中位數 ## 題目地址(295. 數據流的中位數) <https://leetcode-cn.com/problems/find-median-from-data-stream/> ## 題目描述 ``` <pre class="calibre18">``` 中位數是有序列表中間的數。如果列表長度是偶數，中位數則是中間兩個數的平均值。例如， [2,3,4] 的中位數是 3 [2,3] 的中位數是 (2 + 3) / 2 = 2.5 設計一個支持以下兩種操作的數據結構： void addNum(int num) - 從數據流中添加一個整數到數據結構中。 double findMedian() - 返回目前所有元素的中位數。示例： addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 進階: 如果數據流中所有整數都在 0 到 100 范圍內，你將如何優化你的算法？如果數據流中 99% 的整數都在 0 到 100 范圍內，你將如何優化你的算法？ ``` ``` ## 前置知識 - 堆 - 隊列 ## 公司 - 阿里 - 百度 - 字節 ## 思路這道題目是求動態數據的中位數，在 leetcode 難度為`hard`. 如果這道題是求靜態數據的中位數，我們用數組去存儲，空間復雜度 O(1), 時間復雜度 O(1) > 空間復雜度指的是除了存儲數據之外額外開辟的用于計算等任務的內存空間代碼也比較簡單 ``` <pre class="calibre18">``` function findMedian(a) { return a.length % 2 === 0 ? (a[a.length >> 1] + a[a.length >> (1 + 1)]) / 2 : a[a.length >> 1]; } ``` ``` 但是題目要求是動態數據，那么是否可以每次添加數據的時候，都去排一次序呢？假如我們每次插入都用`快速排序`進行排序的話，那么時間復雜度是 O(nlogn) + O(1) > O(nlogn) 是排序的時間復雜度 O(1)是查詢中位數的時間復雜度如果你用這種思路進行的話，恐怕 leetcode 會超時。那么如何優化呢？答案是使用堆， Java， C++等語言都有`優先級隊列`中這種數據結構，優先級隊列本質上就是一個堆。關于堆和優先級隊列的關系，我會放在《數據結構和算法》部分講解。這里不贅述如果借助堆這種數據結構，就可以輕易實現了。具體的做法是，建立兩個堆，這兩個堆需要滿足: 1. 大頂堆元素都比小頂堆小（由于堆的特點其實只要比較堆頂即可） 2. 大頂堆元素不小于小頂堆，且最多比小頂堆多一個元素滿足上面兩個條件的話，如果想要找到中位數，就比較簡單了 - 如果兩個堆數量相等（本質是總數為偶數）, 就兩個堆頂元素的平均數 - 如果兩個堆數量不相等（本質是總數為奇數），就取大頂堆的堆頂元素比如對于\[1,2,3\] 求中位數： ![](https://img.kancloud.cn/ab/9c/ab9ce074ad5a43d9425d85d5d44c450e_828x220.jpg) 再比如對于\[1,2,3, 4\] 求中位數： ![](https://img.kancloud.cn/d6/8d/d68d39b39f00b2f3a6febc0088c97d6e_825x237.jpg) ## 關鍵點解析 - 用兩個堆（一個大頂堆，一個小頂堆）來簡化時間復雜度 - 用優先級隊列簡化操作 > JavaScript 不像 Java， C++等語言都有`優先級隊列`中這種數據結構，因此大家可以使用社區的實現個人認為沒有非要糾結于優先級隊列怎么實現，至少這道題不是考這個的優先級隊列的實現個人認為已經超過了這道題想考察的范疇 > > ## 代碼如果不使用現成的`優先級隊列`這種數據結構，代碼可能是這樣的： ``` <pre class="calibre18">``` /** * initialize your data structure here. */ var MedianFinder = function() { this.maxHeap = []; this.minHeap = []; }; function minHeapify() { this.minHeap.unshift(null); const a = this.minHeap; // 為了方便大家理解，這里選用了粗暴的實現 // 時間復雜度為O(n) // 其實可以降到O(logn)，具體細節我不想在這里講解和實現 for (let i = a.length - 1; i >> 1 > 0; i--) { // 自下往上堆化 if (a[i] < a[i >> 1]) { // 如果子元素更小，則交換位置 const temp = a[i]; this.minHeap[i] = a[i >> 1]; this.minHeap[i >> 1] = temp; } } this.minHeap.shift(null); } function maxHeapify() { this.maxHeap.unshift(null); const a = this.maxHeap; // 為了方便大家理解，這里選用了粗暴的實現 // 時間復雜度為O(n) // 其實可以降到O(logn)，具體細節我不想在這里講解和實現 for (let i = a.length - 1; i >> 1 > 0; i--) { // 自下往上堆化 if (a[i] > a[i >> 1]) { // 如果子元素更大，則交換位置 const temp = a[i]; this.maxHeap[i] = a[i >> 1]; this.maxHeap[i >> 1] = temp; } } this.maxHeap.shift(null); } /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function(num) { // 為了大家容易理解，這部分代碼寫的比較冗余 // 插入 if (num >= (this.minHeap[0] || Number.MIN_VALUE)) { this.minHeap.push(num); } else { this.maxHeap.push(num); } // 調整兩個堆的節點數量平衡 // 使得大頂堆的數量最多大于小頂堆一個，且一定不小于小頂堆數量 if (this.maxHeap.length > this.minHeap.length + 1) { // 大頂堆的堆頂元素移動到小頂堆 this.minHeap.push(this.maxHeap.shift()); } if (this.minHeap.length > this.maxHeap.length) { // 小頂堆的堆頂元素移動到大頂堆 this.maxHeap.push(this.minHeap.shift()); } // 調整堆頂元素 if (this.maxHeap[0] > this.minHeap[0]) { const temp = this.maxHeap[0]; this.maxHeap[0] = this.minHeap[0]; this.minHeap[0] = temp; } // 堆化 maxHeapify.call(this); minHeapify.call(this); }; /** * @return {number} */ MedianFinder.prototype.findMedian = function() { if ((this.maxHeap.length + this.minHeap.length) % 2 === 0) { return (this.minHeap[0] + this.maxHeap[0]) / 2; } else { return this.maxHeap[0]; } }; /** * Your MedianFinder object will be instantiated and called as such: * var obj = new MedianFinder() * obj.addNum(num) * var param_2 = obj.findMedian() */ ``` ``` 其中`minHeapify` 和 `maxHeapify` 的過程都有一個hack操作，就是： ``` <pre class="calibre18">``` this.heap.unshift(null); // .... this.heap.shift(null); ``` ``` 其實就是為了存儲的數據從1開始，這樣方便計算。即對于下標為i的元素， `i >> 1` 一定是父節點的下標。 ![](https://img.kancloud.cn/59/64/5964ac5fcfb8761562bc3f7150e817d2_835x251.jpg) > 這是因為我用滿二叉樹來存儲的堆這個實現比較繁瑣，下面介紹一種優雅的方式，假設JS和Java和C++等語言一樣有`PriorityQueue`這種數據結構，那么我們實現就比較簡單了。代碼： > 關于PriorityQueue的實現，感興趣的可以看下 <https://github.com/janogonzalez/priorityqueuejs> ``` <pre class="calibre18">``` var MedianFinder = function() { this.maxHeap = new PriorityQueue((a, b) => a - b); this.minHeap = new PriorityQueue((a, b) => b - a); }; /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function(num) { // 我們的目標就是建立兩個堆，一個大頂堆，一個小頂堆 // 結合中位數的特點 // 這兩個堆需要滿足: // 1. 大頂堆元素都比小頂堆小（由于堆的特點其實只要比較堆頂即可） // 2. 大頂堆元素不小于小頂堆，且最多比小頂堆多一個元素 // 滿足上面兩個條件的話，如果想要找到中位數，就比較簡單了 // 如果兩個堆數量相等（本質是總數為偶數）, 就兩個堆頂元素的平均數 // 如果兩個堆數量不相等（本質是總數為奇數），就取大頂堆的堆頂元素 // 問題如果保證滿足上述兩個特點 // 1. 保證第一點 this.maxHeap.enq(num); // 由于小頂堆的所有數都來自大頂堆的堆頂元素（最大值） // 因此可以保證第一點 this.minHeap.enq(this.maxHeap.deq()); // 2. 保證第二點 if (this.maxHeap.size() < this.minHeap.size()){ this.maxHeap.enq(this.minHeap.deq()); } }; /** * @return {number} */ MedianFinder.prototype.findMedian = function() { if (this.maxHeap.size() == this.minHeap.size()) return (this.maxHeap.peek() + this.minHeap.peek()) / 2.0; else return this.maxHeap.peek(); }; /** * Your MedianFinder object will be instantiated and called as such: * var obj = new MedianFinder() * obj.addNum(num) * var param_2 = obj.findMedian() */ ``` ```