🔗 UVA-10107 What is the Median?

tags: CPE-241015 CPE-101011 堆積(Heap)

題意

中位數(Median) 在統計學中扮演著重要角色。根據定義，中位數是能將陣列分為兩等份的值。在這道題中，你需要動態地計算一些整數的中位數。例如，假設有五個數字 [1,3,6,2,7][1, 3, 6, 2, 7]，其中 33 是中位數，因為它的兩側各有兩個數字 [1,2][1, 2] 和 [6,7][6, 7]。如果有偶數個值（如 [1,3,6,2,7,8][1, 3, 6, 2, 7, 8]），一個值無法將陣列完全分成兩部分，因此我們會取中間兩個值的平均數 [3,6][3, 6]。因此，中位數將會是 3+62=4.5\frac{3+6}{2} = 4.5。然而，在這道題中，你 只需要輸出中位數的整數部分 ，而不是小數部分。按照題目的要求，中位數應輸出 44。

現在給定連續的整數 xx，對於每個 xx，你需要將 xx 插入到陣列中，並輸出當前陣列的中位數。

約束條件

  • 0≤x<2310 \leq x < 2^{31}，其中 xx 是輸入的數字
  • n<10000n < 10000，其中 nn 是輸入的數字總數

LuckyCat 的中文翻譯

思路：對頂堆積

這是很經典的題目，也就是維護資料流的中位數，通常會使用對頂堆積來解決。

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

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

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

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

  1. 如果當前數量為偶數，即 hp1hp_1 和 hp2hp_2 的大小相同，則我們需要將新元素插入到 hp1hp_1 中。
    • 如果新元素比 hp2hp_2 的堆頂元素還要大，則我們需要將新元素插入到 hp2hp_2 中，並將 hp2hp_2 的堆頂元素移動到 hp1hp_1 中。
    • 否則，直接插入到 hp1hp_1 中。
  2. 如果當前數量為奇數，即 hp1hp_1 比 hp2hp_2 多一個元素，則我們需要將新元素插入到 hp2hp_2 中。
    • 如果新元素比 hp1hp_1 的堆頂元素還要小，則我們需要將新元素插入到 hp1hp_1 中，並將 hp1hp_1 的堆頂元素移動到 hp2hp_2 中。
    • 否則，直接插入到 hp2hp_2 中。

此外，由於在計算中位數時，兩個元素相加可能會導致超過整數範圍，因此我們可以使用 hp1.top() + (hp2.top() - hp1.top()) / 2 來計算中位數，以避免溢位。在 UVA 上的測資並沒有出現，但 CPE 的測資有特別卡掉這種情況。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)，其中 nn 是輸入的數字總數。
    • 每次插入操作的時間複雜度為 O(log⁡n)\mathcal{O}(\log n)，因為插入和取出堆頂元素的操作都是對數時間。
    • 每次查詢中位數的時間複雜度為 O(1)\mathcal{O}(1)。
  • 空間複雜度：O(n)\mathcal{O}(n)。
    • 需要 O(n)\mathcal{O}(n) 的空間來存儲所有輸入的數字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from heapq import *

hp1 = [] # Max Heap, <= median
hp2 = [] # Min Heap, > median

while True:
    try:
        x = int(input().strip())
    except EOFError:
        break

    if len(hp1) == len(hp2): # 當前數量為偶數，加入到左邊
        # 如果新加入的數字比右邊的最小值還要大，則先加入到右邊，再將右邊的最小值加入到左邊
        if hp2 and x > hp2[0]:
            heappush(hp1, -heappushpop(hp2, x))
        # 否則直接加入到左邊
        else:
            heappush(hp1, -x)
    else: # 當前數量為奇數，加入到右邊
        # 如果新加入的數字比左邊的最大值還要小，則先加入到左邊，再將左邊的最大值加入到右邊
        if x < -hp1[0]:
            heappush(hp2, -heappushpop(hp1, -x))
        # 否則直接加入到右邊
        else:
            heappush(hp2, x)

    # 如果兩邊數量相同，則中位數為兩邊堆頂的平均值
    if len(hp1) == len(hp2):
        print((-hp1[0] + hp2[0]) // 2)
    # 否則中位數為左邊堆頂的值
    else:
        print(-hp1[0])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int x;
    priority_queue<int> hp1; // max heap, <= median
    priority_queue<int, vector<int>, greater<int>> hp2; // min heap, > median
    while (cin >> x) {
        if (hp1.size() == hp2.size()) {
            if (!hp2.empty() && x > hp2.top()) {
                hp1.push(hp2.top());
                hp2.pop();
                hp2.push(x);
            } else {
                hp1.push(x);
            }
        } else {
            if (x < hp1.top()) {
                hp2.push(hp1.top());
                hp1.pop();
                hp1.push(x);
            } else {
                hp2.push(x);
            }
        }
        if (hp1.size() == hp2.size()) {
            // cout << (hp1.top() + hp2.top()) / 2 << endl;
            cout << hp1.top() + (hp2.top() - hp1.top()) / 2 << endl; // avoid overflow
        } else {
            cout << hp1.top() << endl;
        }
    }
    return 0;
}

類題

題單來自 @灵茶山艾府

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

(1girl, solo), Frieren, frieren, long hair, very long hair, (green eyes:1.5), grey hair, pointy ears, elf,

dress, white dress, sleeveless, sleeveless dress, jewelry, earrings, bare shoulders, parted bangs, bare arms, barefoot, bare legs, collarbone, looking at viewer, blush, sitting, closed mouth, full body, flower, water, wariza, strap slip, between legs, hand between legs, lily pad,

anime girl, sitting in water, white dress, pointed ears, floating flowers, serene, fantasy, soft lighting, dreamy atmosphere,

第二題就是 LeetCode Hard 等級的題目，CPE 最狠的一次。