優先隊列題目：資料流的中位數

文章目錄

• 題目
• • 标題和出處
  • 難度
  • 題目描述
  • • 要求
    • 示例
    • 資料範圍
    • 進階
• 解法
• • 思路和算法
  • 代碼
  • 複雜度分析
• 進階問題答案

題目

标題和出處

标題：資料流的中位數

出處：295. 資料流的中位數

難度

6 級

題目描述

要求

中位數是有序整數清單的中間的數。如果清單長度是偶數，則沒有中間的數，此時中位數是中間的兩個數的平均值。

• 例如， arr = [2,   3,   4] \texttt{arr} = \texttt{[2, 3, 4]} arr=[2, 3, 4] 的中位數是 3 \texttt{3} 3。
• 例如， arr = [2,   3] \texttt{arr} = \texttt{[2, 3]} arr=[2, 3] 的中位數是 3 2 = 2.5 \dfrac{\texttt{3}}{\texttt{2}} = \texttt{2.5} 23​=2.5。

實作 MedianFinder \texttt{MedianFinder} MedianFinder 類：

• MedianFinder() \texttt{MedianFinder()} MedianFinder() 初始化 MedianFinder \texttt{MedianFinder} MedianFinder 對象。
• void   addNum(int   num) \texttt{void addNum(int num)} void addNum(int num) 将資料流中的整數 num \texttt{num} num 添加到資料結構。
• double   findMedian() \texttt{double findMedian()} double findMedian() 傳回目前所有元素的中位數。和正确答案的誤差不超過 10 -5 \texttt{10}^\texttt{-5} 10-5 的答案被視為正确答案。

示例

示例 1：

輸入：

["MedianFinder",   "addNum",   "addNum",   "findMedian",   "addNum",   "findMedian"] \texttt{["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]} ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]

[[],   [1],   [2],   [],   [3],   []] \texttt{[[], [1], [2], [], [3], []]} [[], [1], [2], [], [3], []]

輸出：

[null,   null,   null,   1.5,   null,   2.0] \texttt{[null, null, null, 1.5, null, 2.0]} [null, null, null, 1.5, null, 2.0]

解釋：

MedianFinder   medianFinder   =   new   MedianFinder(); \texttt{MedianFinder medianFinder = new MedianFinder();} MedianFinder medianFinder = new MedianFinder();

medianFinder.addNum(1); \texttt{medianFinder.addNum(1);} medianFinder.addNum(1); // arr   =   [1] \texttt{arr = [1]} arr = [1]

medianFinder.addNum(2); \texttt{medianFinder.addNum(2);} medianFinder.addNum(2); // arr   =   [1,   2] \texttt{arr = [1, 2]} arr = [1, 2]

medianFinder.findMedian(); \texttt{medianFinder.findMedian();} medianFinder.findMedian(); // 傳回 1.5 \texttt{1.5} 1.5

medianFinder.addNum(3); \texttt{medianFinder.addNum(3);} medianFinder.addNum(3); // arr   =   [1,   2,   3] \texttt{arr = [1, 2, 3]} arr = [1, 2, 3]

medianFinder.findMedian(); \texttt{medianFinder.findMedian();} medianFinder.findMedian(); // 傳回 2.0 \texttt{2.0} 2.0

資料範圍

• -10 5 ≤ num ≤ 10 5 \texttt{-10}^\texttt{5} \le \texttt{num} \le \texttt{10}^\texttt{5} -105≤num≤105
• 在調用 findMedian \texttt{findMedian} findMedian 方法之前，資料結構中至少有一個元素
• 最多調用 addNum \texttt{addNum} addNum 和 findMedian \texttt{findMedian} findMedian 方法 5 × 10 4 \texttt{5} \times \texttt{10}^\texttt{4} 5×104 次

進階

• 如果資料流中所有整數都在範圍 [0,   100] \texttt{[0, 100]} [0, 100] 内，你将如何優化你的算法？
• 如果資料流中 99% \texttt{99\%} 99% 的整數都在範圍 [0,   100] \texttt{[0, 100]} [0, 100] 内，你将如何優化你的算法？

解法

思路和算法

根據中位數的定義，中位數的值取決于有序清單的中間的一個數或兩個數。為了得到資料流的中位數，需要設計一種滿足以下要求的資料結構：

1. 該資料結構能維護元素的有序性（或者部分有序性），支援快速定位到中間元素；
2. 該資料結構支援快速添加元素，且添加元素之後仍能滿足第 1 點要求。

滿足上述要求的資料結構為優先隊列，優先隊列支援在對數時間複雜度内添加元素和在常數時間内擷取隊首元素。

根據優先隊列的性質，為了得到資料流的中位數，需要建立兩個優先隊列分别存儲較小的一半元素和較大的一半元素。存儲較小的一半元素的優先隊列是 lower \textit{lower} lower，基于大頂堆實作，隊首元素是優先隊列中的最大元素；存儲較大的一半元素的優先隊列是 higher \textit{higher} higher，基于小頂堆實作，隊首元素是優先隊列中的最小元素。兩個優先隊列滿足以下要求：

• 優先隊列 lower \textit{lower} lower 的隊首元素小于等于優先隊列 higher \textit{higher} higher 的隊首元素；
• 優先隊列 lower \textit{lower} lower 的元素個數大于等于優先隊列 higher \textit{higher} higher 的元素個數；
• 兩個優先隊列的元素個數之差不超過 1 1 1。

為了滿足上述要求，添加整數的操作如下：

• 如果資料流中的整數個數是偶數，首先将添加的整數加入 higher \textit{higher} higher，然後将 higher \textit{higher} higher 的隊首整數取出并将取出的整數加入 lower \textit{lower} lower；
• 如果資料流中的整數個數是奇數，首先将添加的整數加入 lower \textit{lower} lower，然後将 lower \textit{lower} lower 的隊首整數取出并将取出的整數加入 higher \textit{higher} higher。

當兩個優先隊列滿足上述要求時，即可通過兩個優先隊列的隊首元素計算中位數：

• 如果資料流中的整數個數是偶數，則兩個優先隊列的元素個數相等，中位數等于兩個優先隊列的隊首元素的平均值；
• 如果資料流中的整數個數是奇數，則 lower \textit{lower} lower 比 higher \textit{higher} higher 多一個元素，中位數等于 lower \textit{lower} lower 的隊首元素。

代碼

class MedianFinder {
    PriorityQueue<Integer> lower;
    PriorityQueue<Integer> higher;
    int size;

    public MedianFinder() {
        lower = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        higher = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num1 - num2;
            }
        });
        size = 0;
    }

    public void addNum(int num) {
        if (size % 2 == 0) {
            higher.offer(num);
            lower.offer(higher.poll());
        } else {
            lower.offer(num);
            higher.offer(lower.poll());
        }
        size++;
    }

    public double findMedian() {
        return size % 2 == 0 ? (lower.peek() + higher.peek()) / 2.0 : lower.peek();
    }
}
           

複雜度分析

• 時間複雜度：構造方法和計算中位數操作的時間複雜度是 O ( 1 ) O(1) O(1)，添加整數操作的時間複雜度是 O ( log ⁡ n ) O(\log n) O(logn)，其中 n n n 是資料流中的整數個數。

  添加整數操作需要對其中一個優先隊列進行添加元素和删除元素操作，對另一個優先隊列進行添加元素操作，是以時間複雜度是 O ( log ⁡ n ) O(\log n) O(logn)。

  計算中位數操作隻要得到優先隊列的隊首元素即可計算，得到優先隊列的隊首元素的時間複雜度是 O ( 1 ) O(1) O(1)。

• 空間複雜度： O ( n ) O(n) O(n)，其中 n n n 是資料流中的整數個數。空間複雜度主要取決于兩個優先隊列空間，兩個優先隊列存儲資料流中的全部整數。

進階問題答案

第一個進階問題，如果資料流中所有整數都在範圍 [ 0 , 100 ] [0, 100] [0,100] 内，則可以使用計數排序統計每個整數的個數，并根據資料流中的整數個數，使用雙指針維護中位數。

第二個進階問題，如果資料流中 99 % 99\% 99% 的整數都在範圍 [ 0 , 100 ] [0, 100] [0,100] 内，則仍然可以使用計數排序統計每個整數的個數，并根據資料流中的整數個數，使用雙指針維護中位數。對于小于 0 0 0 或大于 100 100 100 的整數，分别使用兩個數組存儲即可。如果中位數小于 0 0 0 或大于 100 100 100，則隻需要在對應的數組中計算中位數即可，由于大多數情況下中位數都在範圍 [ 0 , 100 ] [0, 100] [0,100] 内，是以中位數小于 0 0 0 或大于 100 100 100 的情況是極少數，此時使用暴力解法不會影響總體時間複雜度。