[[431427]]

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

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

例如，

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

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

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

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

示例：

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

進(jìn)階:

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

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

解法：利用堆

解題思路：

這里需要維護(hù)兩個(gè)堆：

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

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

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

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

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

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

代碼實(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 = [,] 
    // 堆中元素?cái)?shù)量 
    this.getSize = ()=> heap.length - 1 
    // 插入 
    this.insert = (key) => { 
        heap.push(key) 
        // 獲取存儲(chǔ)位置 
        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 = [,] 
    // 堆中元素?cái)?shù)量 
    this.getSize = ()=>heap.length - 1 
    // 插入大頂堆 
    this.insert = (key) => { 
        heap.push(key) 
        // 獲取存儲(chǔ)位置 
        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ù)雜度分析：

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

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

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

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