劍指 Offer 41. 資料流中的中位數

題目

如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那麼中位數就是所有數值排序之後位于中間的數值。如果從資料流中讀出偶數個數值，那麼中位數就是所有數值排序之後中間兩個數的平均值。

例如，

[2,3,4] 的中位數是 3

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

設計一個支援以下兩種操作的資料結構：

• void addNum(int num) - 從資料流中添加一個整數到資料結構中。
• double findMedian() - 傳回目前所有元素的中位數。

示例 1：

輸入：[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”]

[[],[1],[2],[],[3],[]]

輸出：[null,null,null,1.50000,null,2.00000]

示例 2：

輸入： [“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”]

[[],[2],[],[3],[]]

輸出：[null,null,2.00000,null,2.50000]

限制：

• 最多會對 addNum、findMedian 進行 50000 次調用。

來源：力扣（LeetCode）

連結：​​​https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof​​

解題思路

• 數組大小為奇數,就是中間的那一個數
• 數組大小為偶數,就是中間的兩個數的平均值

• 一個大頂堆加上一個小頂堆可以當做一個有序數組
• 大頂堆作為數組的前半段,存儲數組中較小的元素
• 小頂堆作為數組的後半段,存儲數組中較大的元素
• 當數組的大小為偶數時,大頂堆和小頂堆的大小相等
• 當數組的大小為奇數時,可以約定奇數放在大頂堆還是小頂堆,這個都随意,代碼不同
• 建立一個大頂堆a和小頂堆b
• 假設大頂堆a的大小為n,小頂堆b的大小為m,我們約定

• 數組大小為偶數時n == m,
• 數組大小為奇數時n == m + 1

• 添加元素時

• 當n != m時,此時說明數組大小為奇數,添加一個元素變為偶數,則需要轉換成n == m,即小頂堆元素+1

• 小頂堆存儲數組的後半段,存儲數組中較大的元素,待添加元素和大頂堆堆頂元素中較大的元素入大頂堆
• 待添加元素,入堆大頂堆
• 大頂堆堆頂元素入堆小頂堆

• 當n == m時,此時說明數組大小為偶數,添加一個元素變為奇數,則需要轉換成n == m + 1,即大頂堆元素+1

• 大頂堆存儲數組的前半段,存儲數組中較小的元素,待添加元素和小頂堆堆頂元素中較小的元素入小頂堆
• 待添加元素,入堆小頂堆
• 小頂堆堆頂元素入堆大頂堆

• 擷取中位數時

• 當n != m時,直接傳回大頂堆的堆頂元素
• 當n == m時,傳回大頂堆堆頂元素和小頂堆堆頂元素,取平均值

代碼

class MedianFinder {

    // 維護兩個堆
    PriorityQueue<Integer> a;
    PriorityQueue<Integer> b;
    /** initialize your data structure here. */
    public MedianFinder() {
        // 其中a為大頂堆,b為小頂堆
        // 大頂堆存儲有序數組中較小的元素,小頂堆存儲有序數組中較大的元素
        // 可以了解為大頂堆a是有序數組的前半段,小頂堆b是有序數組的後半段
        a = new PriorityQueue<>((v1, v2) -> v2 - v1);
        b = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        // 假設a堆大小為n,b堆大小為m,約定n == m,或者n == m + 1
        if (a.size() != b.size()) {
            // 當a堆和b堆大小不相等時,依據約定此時n == m + 1
            // 轉移成n == m,則此時需要n不變,m + 1
            // b堆中儲存數組中較大的元素,是以需要添加的是num和大頂堆a堆頂元素中的最大值
            // 元素加入a堆,然後把a堆堆頂的元素,即最大值入b堆
            a.add(num);
            b.add(a.poll());
        } else {
            // 當a堆和b堆大小相等時,依據約定此時n == m
            // 轉移成n == m + 1,則此時需要m不變,n + 1
            // a堆中儲存數組中較小的元素,是以需要添加的是num和小頂堆b堆頂元素中的最小值
            // 元素加入b堆,然後把b堆堆頂的元素,即最小值入a堆
            b.add(num);
            a.add(b.poll());
        }
    }
    
    public double findMedian() {
        if (a.size() != b.size()) {
            // a堆和b堆大小不相等,直接取a堆堆頂元素傳回
            return a.peek();
        } else {
            // a堆和b堆大小相等,取兩個堆頂元素相加再除以2.0
            return (a.peek() + b.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();
 */      

複雜度

• 時間複雜度:

• 添加: O(logn),堆的插入和彈出操作使用 O(\log N)O(logN) 時間
• 查找:O(1),擷取堆頂元素使用O(1)時間

• 空間複雜度:O(n),維護數組元素