480. Медиана скользящего окна (Sliding Window Median)

Задание.

Медиана – это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, то среднего значения нет. Таким образом, медиана – это среднее из двух средних значений.

• Например, если arr = [2,3,4], медиана равна 3.

• Например, если arr = [1, 2,3,4], медиана равна (2 + 3) / 2 = 2.5.

Вам дается целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается из самого левого края массива в самый правый. Вы можете видеть только k чисел в окне. Каждый раз, когда раздвижное окно перемещается вправо на одну позицию.

Верните массив медиан для каждого окна в исходном массиве. Будут приняты ответы в пределах 10^-5 от фактического значения.

Пример 1.

Входные данные: nums = [1,3,-1,-3,5,3,6,7], k = 3

Результат: [1.00000, -1.00000, -1.00000, 3.00000, 5.00000, 6.00000]

Пояснение:

Window position                Median
---------------                -----
[1  3  -1] -3  5  3  6  7        1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7        3
 1  3  -1  -3 [5  3  6] 7        5
 1  3  -1  -3  5 [3  6  7]       6

Пример 2.

Входные данные: nums = [1,2,3,4,2,3,1,4,2], k = 3

Результат: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]

Решение.

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        
    }
};

Способ решения.