#LAISIR12. 滑動窗口中位數查詢(Sliding Median)
滑動窗口中位數查詢(Sliding Median)
題目名稱:滑動窗口中位數查詢(Sliding Median)
題目描述:
給定一個長度為 的整數序列 ,以及一個整數 ,表示滑動窗口的大小。
請你計算每個長度為 的連續子序列的中位數。
中位數定義如下:
若子序列長度為奇數,則中位數為排序後的中間元素。
若子序列長度為偶數,則中位數為排序後靠左的中間元素(即第 小的元素)。
輸入格式:
第一行包含兩個整數 和 ,表示序列的長度和滑動窗口的大小。
第二行包含 個整數 ,表示序列中的元素。
輸出格式:
輸出共 行,每行一個整數,依序表示每個滑動窗口的中位數。
範例輸入:
7 3
1 3 -1 -3 5 3 6
範例輸出:
1
-1
-1
3
5
📘 說明: 對於給定的序列和窗口大小,滑動窗口的位置及其對應的中位數如下:
窗口 [1, 3, -1] → 排序後 [-1, 1, 3] → 中位數為 1
窗口 [3, -1, -3] → 排序後 [-3, -1, 3] → 中位數為 -1
窗口 [-1, -3, 5] → 排序後 [-3, -1, 5] → 中位數為 -1
窗口 [-3, 5, 3] → 排序後 [-3, 3, 5] → 中位數為 3
窗口 [5, 3, 6] → 排序後 [3, 5, 6] → 中位數為 5
📌 限制條件:
Related
In following homework: