Войти Регистрация
Алгоритмы

144. Медиана платежа за последние k операций

Сложная

Антифрод Сбера сравнивает новый платёж клиента с медианой последних k платежей: среднее арифметическое портит одна покупка машины, медиана — нет.

Дан список сумм amounts в рублях по времени и размер окна k. Для каждого окна amounts[i..i+k-1] верните нижнюю медиану — элемент с номером (k − 1) // 2 (с нуля) в отсортированном окне. Всего n − k + 1 значений.

В работе: Платёж в 20 раз выше медианы последних 30 операций — повод спросить подтверждение в СМС.

Пример 1

Ввод
amounts = [500, 1200, 300, 300, 90000, 700, 800]
k = 3
Вывод
[500, 300, 300, 700, 800]

Окно [500, 1200, 300] → 500; покупка за 90 000 медиану почти не сдвигает.

Пример 2

Ввод
amounts = [400, 100, 300, 200]
k = 2
Вывод
[100, 100, 200]

При чётном k берём меньший из двух средних.

Ограничения

  • 1 ≤ k ≤ n ≤ 10⁵
  • 1 ≤ amounts[i] ≤ 10⁹
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def window_medians(amounts, k):
КучаДве кучиЛенивое удалениеСкользящее окноцельO(n log n)

Источник: наша задача на данных Сбера. Условие пересказано своими словами.