[[431427]]

本文轉(zhuǎn)載自微信公眾號「三分鐘學(xué)前端」，作者sisterAn  。轉(zhuǎn)載本文請聯(lián)系三分鐘學(xué)前端公眾號。

中位數(shù)是有序列表中間的數(shù)。如果列表長度是偶數(shù)，中位數(shù)則是中間兩個數(shù)的平均值。

例如，

[2,3,4] 的中位數(shù)是 3

[2,3] 的中位數(shù)是 (2 + 3) / 2 = 2.5

設(shè)計一個支持以下兩種操作的數(shù)據(jù)結(jié)構(gòu)：

• void addNum(int num)- 從數(shù)據(jù)流中添加一個整數(shù)到數(shù)據(jù)結(jié)構(gòu)中。
• double findMedian() - 返回目前所有元素的中位數(shù)。

示例：

addNum(1) 
addNum(2) 
findMedian() -> 1.5 
addNum(3)  
findMedian() -> 2 

進階:

• 如果數(shù)據(jù)流中所有整數(shù)都在 0 到 100 范圍內(nèi)，你將如何優(yōu)化你的算法?
• 如果數(shù)據(jù)流中 99% 的整數(shù)都在 0 到 100 范圍內(nèi)，你將如何優(yōu)化你的算法?

看到這個動態(tài)數(shù)組獲取中位數(shù)問題，不要太激動，這太適合使用堆了，考察的就是堆的經(jīng)典應(yīng)用：中位數(shù)問題，詳情可查看 前端進階算法9：看完這篇，再也不怕堆排序、Top K、中位數(shù)問題面試了

解法：利用堆

解題思路：

這里需要維護兩個堆：

• 大頂堆：用來存取前 n/2 個小元素，如果 n 為奇數(shù)，則用來存取前 Math.floor(n/2) + 1 個元素
• 小頂堆：用來存取后 n/2 個小元素

那么，根據(jù)題目要求，中位數(shù)就為：

• n 為奇數(shù)：中位數(shù)是大頂堆的堆頂元素
• n 為偶數(shù)：中位數(shù)是大頂堆的堆頂元素與小頂堆的堆頂元素的平均值

當(dāng)數(shù)組為動態(tài)數(shù)組時，每當(dāng)數(shù)組中插入一個元素時，都需要如何調(diào)整堆喃?

如果插入元素比大頂堆的堆頂要大，則將該元素插入到小頂堆中;如果要小，則插入到大頂堆中。

當(dāng)插入完成后，如果大頂堆、小頂堆中元素的個數(shù)不滿足我們已上的要求，我們就需要不斷的將大頂堆的堆頂元素或小頂堆的堆頂元素移動到另一個堆中，直到滿足要求

代碼實現(xiàn)：

let MedianFinder = function() { 
    // 大頂堆，用來保存前 n/2 小的元素 
    this.lowHeap = new MaxHeap() 
    // 小頂堆，用來保存后 n/2 小的元素 
    this.hightHeap = new MinHeap() 
}; 
// 插入元素 
MedianFinder.prototype.addNum = function(num) { 
    // 如果大頂堆為空或大頂堆堆頂元素小于num，則插入大頂堆 
    // 否則插入到小頂堆中 
    if(!this.lowHeap.getSize() || num < this.lowHeap.getHead()) { 
        // 比大頂堆的堆頂小，插入到大頂堆中 
        this.lowHeap.insert(num) 
    } else { 
        // 比小頂堆的堆頂大，插入到小頂堆中 
        this.hightHeap.insert(num) 
    } 
 
    // 比較大小頂堆的是否依然保持平衡 
    if(this.lowHeap.getSize() - this.hightHeap.getSize() > 1) { 
        // 大頂堆往小頂堆遷移 
        this.hightHeap.insert(this.lowHeap.removeHead()) 
    } 
    if(this.hightHeap.getSize() > this.lowHeap.getSize()) { 
        // 小頂堆向大頂堆遷移 
        this.lowHeap.insert(this.hightHeap.removeHead()) 
    } 
}; 
// 獲取中位數(shù) 
MedianFinder.prototype.findMedian = function() { 
    if(this.lowHeap.getSize() && this.lowHeap.getSize() === this.hightHeap.getSize()) { 
        return (this.lowHeap.getHead() + this.hightHeap.getHead())/2 
    } 
    return this.lowHeap.getHead() 
}; 

其中小頂堆定義：

// 小頂堆 
let MinHeap = function() { 
    let heap = [,] 
    // 堆中元素數(shù)量 
    this.getSize = ()=> heap.length - 1 
    // 插入 
    this.insert = (key) => { 
        heap.push(key) 
        // 獲取存儲位置 
        let i = heap.length-1 
        while (Math.floor(i/2) > 0 && heap[i] < heap[Math.floor(i/2)]) {   
            swap(heap, i, Math.floor(i/2)); // 交換  
            i = Math.floor(i/2);  
        } 
    } 
    // 刪除堆頭并返回 
    this.removeHead = () => { 
        if(heap.length > 1) { 
            if(heap.length === 2) return heap.pop() 
            let num = heap[1] 
            heap[1] = heap.pop() 
            heapify(1) 
            return num 
        } 
        return null 
    } 
    // 獲取堆頭 
    this.getHead = () => { 
        return heap.length > 1 ? heap[1]:null 
    } 
    // 堆化 
    let heapify = (i) => { 
        let k = heap.length-1 
        // 自上而下式堆化 
        while(true) { 
            let minIndex = i 
            if(2*i <= k && heap[2*i] < heap[i]) { 
                minIndex = 2*i 
            } 
            if(2*i+1 <= k && heap[2*i+1] < heap[minIndex]) { 
                minIndex = 2*i+1 
            } 
            if(minIndex !== i) { 
                swap(heap, i, minIndex) 
                i = minIndex 
            } else { 
                break 
            } 
        } 
    }  
    let swap = (arr, i, j) => { 
        let temp = arr[i] 
        arr[i] = arr[j] 
        arr[j] = temp 
    } 
} 

大頂堆定義：

// 大頂堆 
let MaxHeap = function() { 
    let heap = [,] 
    // 堆中元素數(shù)量 
    this.getSize = ()=>heap.length - 1 
    // 插入大頂堆 
    this.insert = (key) => { 
        heap.push(key) 
        // 獲取存儲位置 
        let i = heap.length-1 
        while (Math.floor(i/2) > 0 && heap[i] > heap[Math.floor(i/2)]) {   
            swap(heap, i, Math.floor(i/2)); // 交換  
            i = Math.floor(i/2);  
        } 
    } 
    // 獲取堆頭 
    this.getHead = () => { 
        return heap.length > 1 ? heap[1]:null 
    } 
    // 刪除堆頭并返回 
    this.removeHead = () => { 
        if(heap.length > 1) { 
            if(heap.length === 2) return heap.pop() 
            let num = heap[1] 
            heap[1] = heap.pop() 
            heapify(1) 
            return num 
        } 
        return null 
    } 
    // 堆化 
    let heapify = (i) => { 
        let k = heap.length-1 
        // 自上而下式堆化 
        while(true) { 
            let maxIndex = i 
            if(2*i <= k && heap[2*i] > heap[i]) { 
                maxIndex = 2*i 
            } 
            if(2*i+1 <= k && heap[2*i+1] > heap[maxIndex]) { 
                maxIndex = 2*i+1 
            } 
            if(maxIndex !== i) { 
                swap(heap, i, maxIndex) 
                i = maxIndex 
            } else { 
                break 
            } 
        } 
    }  
    let swap = (arr, i, j) => { 
        let temp = arr[i] 
        arr[i] = arr[j] 
        arr[j] = temp 
    } 
} 

復(fù)雜度分析：

時間復(fù)雜度：由于插入元素到堆的時間復(fù)雜度為 O(logn)，為樹的高度;移動堆頂元素都需要堆化，時間復(fù)雜度也為O(logn);所以，插入( addNum )的時間復(fù)雜度為 O(logn) ，每次插入完成后求中位數(shù)僅僅需要返回堆頂元素即可， findMedian 時間復(fù)雜度為 O(1)

空間復(fù)雜度：O(n)

如果數(shù)據(jù)流中所有整數(shù)都在 0 到 100 范圍內(nèi)，我們可以嘗試使用計數(shù)排序，但計數(shù)排序的時間復(fù)雜度是O(n + m)，其中 m 表示數(shù)據(jù)范圍，復(fù)雜度較高，這里不適合，計數(shù)排序比較適合靜態(tài)數(shù)組前k個最值問題 leetcode347：前 K 個高頻元素

leetcode：https://leetcode-cn.com/problems/find-median-from-data-stream/solution/javascriptshu-ju-liu-de-zhong-wei-shu-by-user7746o/