🔗 🔴 295. Find Median from Data Stream

題意

中位數(Median) 是有序整數列表中的中間值。如果列表的大小是偶數，則定義中位數是兩個中間值的平均值。

例如 $[2, 3, 4]$ 的中位數是 $3$ 。
例如 $[2, 3]$ 的中位數是 $\frac{2+3}{2} = 2.5$ 。

請你實現 MedianFinder 類別：

MedianFinder() 初始化 MedianFinder 對象。
void addNum(int num) 從資料流(Data Stream) 中添加整數 num 到數據結構中。
double findMedian() 返回目前所有元素的中位數。與實際答案誤差相在在 $10^{-5}$ 之內的答案將被接受。

約束條件

$-10^5 \leq num \leq 10^5$
在調用 findMedian 之前，數據結構中至少會有一個元素。
最多會調用 $5 \times 10^4$ 次 addNum 和 findMedian。

思路：對頂堆積

首先我們考慮最暴力的做法，即每次 addNum 後，將所有元素排序，然後計算中位數；或是在遇到 findMedian 時，將所有元素排序，然後計算中位數。但不管如何，這麼做都會導致其中一種操作的時間複雜度為 $O(n \log n)$ ，在無法保證操作是如何分布的情況下，會導致最壞情況下的時間複雜度為 $O(n^2 \log n)$ ，這樣的時間複雜度顯然不夠高效。而根據題目的資料範圍，我們需要找到一個插入和查詢都是 $O(\log n)$ 的解法。

那我們不妨從中位數的定義下手，中位數是有序整數列表中的中間值，這代表了中位數左邊會有 $\frac{n}{2}$ 個元素，右邊也會有 $\frac{n}{2}$ 個元素。那麼我們可以嘗試使用兩個容器維護這兩個部分，並在插入新元素時，維持兩個容器的大小關係。

雖然可以用在有序列表中二分查找插入位置，或是直接使用有序容器如 multiset 或 SortedList 的方式來維護，但通常會使用對頂堆積來解決。

具體來說，我們會使用兩個堆積，使其滿足以下性質：

$hp_1$ ：最大堆積，用來存儲 $\leq {Median}$ 的一半數字，其堆頂是這一半數字中的最大值。
$hp_2$ ：最小堆積，用來存儲 $> {Median}$ 的一半數字，其堆頂是這一半數字中的最小值。

根據以上的性質，我們可以知道，如果兩個堆積的大小相同，中位數就是兩個堆頂元素的平均值；反之，如果兩個堆積的大小不同，中位數就是 $hp_1$ 的堆頂元素。

而在插入新元素的時候，我們需要使兩個堆積保持前述的性質，具體步驟如下：

如果當前數量為偶數，即 $hp_1$ $h p_{1}$ 和 $hp_2$ $h p_{2}$ 的大小相同，則我們需要將新元素插入到 $hp_1$ $h p_{1}$ 中。
- 如果新元素比 $hp_2$ 的堆頂元素還要大，則我們需要將新元素插入到 $hp_2$ 中，並將 $hp_2$ 的堆頂元素移動到 $hp_1$ 中。
- 否則，可以直接插入到 $hp_1$ 中，但由於新元素一定比 $hp_2$ 的所有元素小，因此這其實也等同上述插入後再移動的操作。
如果當前數量為奇數，即 $hp_1$ $h p_{1}$ 比 $hp_2$ $h p_{2}$ 多一個元素，則我們需要將新元素插入到 $hp_2$ $h p_{2}$ 中。
- 如果新元素比 $hp_1$ 的堆頂元素還要小，則我們需要將新元素插入到 $hp_1$ 中，並將 $hp_1$ 的堆頂元素移動到 $hp_2$ 中。
- 否則，直接插入到 $hp_2$ 中，但類似地，這其實也等同上述插入後再移動的操作。

此外，雖然 LeetCode 的測資範圍內不會有這種情況，但若 $num$ 的值域和整數範圍相同，則在計算中位數時，兩個整數元素相加可能會導致超過整數範圍，因此我們可以使用 hp1.top() + (hp2.top() - hp1.top()) / 2 來計算中位數。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ $O (n lo g n)$ ，其中 $n$ $n$ 是輸入的數字總數。
- 每次插入操作的時間複雜度為 $\mathcal{O}(\log n)$ ，因為插入元素和彈出堆頂元素的操作都是 $\mathcal{O}(\log n)$ 時間。
- 每次查詢中位數的時間複雜度為 $\mathcal{O}(1)$ 。
空間複雜度： $\mathcal{O}(n)$ $O (n)$ 。
- 需要 $\mathcal{O}(n)$ 的空間來存儲所有輸入的數字。

class MedianFinder:

    def __init__(self):
        # max heap，保存 <= median 的數字
        self.l = []
        # min heap，保存 > median 的數字
        self.r = []

    def addNum(self, num: int) -> None:
        # 當前數量為偶數，加入到左邊
        if len(self.l) == len(self.r):
            # 如果新加入的數字比右邊的最小值還要大，則先加入到右邊，再將右邊的最小值加入到左邊
            if self.r and num > self.r[0]:
                heappush(self.l, -heappushpop(self.r, num))
            else:
                heappush(self.l, -num)
        # 當前數量為奇數，加入到右邊
        else:
            # 如果新加入的數字比左邊的最大值還要小，則先加入到左邊，再將左邊的最大值加入到右邊
            if num < -self.l[0]:
                heappush(self.r, -heappushpop(self.l, -num))
            else:
                heappush(self.r, num)

    def findMedian(self) -> float:
        return (-self.l[0] + self.r[0]) / 2 if len(self.l) == len(self.r) else -self.l[0]

class MedianFinder {
 public:
  // max heap，保存 <= median 的數字
  priority_queue<int> l;
  // min heap，保存 > median 的數字
  priority_queue<int, vector<int>, greater<int>> r;

  MedianFinder() {}

  void addNum(int num) {
    // 若當前數量為偶數，則應該將新數字加入到左邊
    if (l.size() == r.size()) {
      // 如果新數字比右邊的最小值還要大，則把右邊的最小值加入到左邊、把新數字加入到右邊
      if (!r.empty() && num > r.top()) {
        l.push(r.top()); r.pop();
        r.push(num);
      } else {
        l.push(num);
      }
      // 若當前數量為奇數，則應該將新數字加入到右邊
    } else {
      // 如果新數字比左邊的最大值還要小，則把左邊的最大值加入到右邊、把新數字加入到左邊
      if (num < l.top()) {
        r.push(l.top()); l.pop();
        l.push(num);
      } else {
        r.push(num);
      }
    }
  }

  double findMedian() {
    return l.size() == r.size() ? l.top() + (r.top() - l.top()) / 2.0 : l.top();
  }
};

Follow-up

如果資料流(Data Stream)中的所有整數都在範圍 $[0, 100]$ 內，你將如何優化你的解決方案？

由於所有整數都在範圍 $[0, 100]$ 內，因此我們可以利用計數排序(Counting Sort) 統計每一個數字的數量，併類似前述對頂堆的思路，將數列分成兩個部分，並使用雙指針(Two Pointers) 維護中位數。

如果資料流(Data Stream)中的 $99\%$ 的整數都在範圍 $[0, 100]$ 內，你又會如何優化你的解決方案？

由於 $99\%$ 的整數都在範圍 $[0, 100]$ 內，因此我們還是可以利用計數排序(Counting Sort) 統計 $[0, 100]$ 內的數字數量。對於超出範圍的數字，則可以使用暴力檢查，或是依然用對頂堆進行處理。

類題

🟢 703. Kth Largest Element in a Stream
🔴 480. Sliding Window Median
🔴 2102. Sequentially Ordinal Rank Tracker 2159
🔴 3013. Divide an Array Into Subarrays With Minimum Cost II 2540

題單來自 @灵茶山艾府

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail,

1other, solo, no humans, Sylveon, Sylveon (Pokémon), Pokémon, blue eyes, full body, flowing ribbons,

dreamy atmosphere, pastel colors, soft lighting, cherry blossom petals floating, fluffy clouds, rainbow in sky, glowing butterflies, sparkles, magical forest, fairy lights, flower field, morning dew, cotton candy clouds, lens flare, depth of field, ethereal glow, spring season,

最近會更新一些研究所考試中出現過的演算法題目，如果有想看的題目也可以留言告訴我，因為不保證所有題目我都能找到 Online Judge 可以測試，所以還是以有 Online Judge 的題目為主。