Kth Largest Element in a Stream

Лёгкая№703k наибольших

Нужно написать класс: он получает число k и начальный список чисел, а потом новые числа по одному. После каждого нового числа он возвращает k-е по величине среди всех чисел, что видел, повторы считаются. Наш пример: k = 3, список [6, 2, 9, 4, 1], затем add(5), add(3), add(10) — они возвращают 5, 5 и 6.

703 Kth Largest Element in a StreamРазбор · 1×

Пример: k = 3, nums = [6, 2, 9, 4, 1], затем add(5), add(3), add(10). Сверху — числа в том порядке, в каком их получает класс; ниже — мин-куча.

numsadd(val)629415310мин-кучаk = 3add вернул—
ещё не пришлоval, только что положилив кучекорень, сейчас уйдётубраноk-е по величине, возвращаем

Создаём KthLargest(3, [6, 2, 9, 4, 1]): init выполняется один раз

01/22
сначала · назад · пуск · шаг
Скорость
1class KthLargest:
2 function init(k, nums):
3 heap = min-heap of nums
4 while size of heap > k:
5 pop min from heap
6 function add(val):
7 push val into heap
8 if size of heap > k:
9 pop min from heap
10 return min of heap
состояние
k
3
val
–
heap
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. В куче всегда k самых больших из уже пришедших чисел. Наверху — меньшее из них, а это и есть k-е по величине.
  2. Число меньше корня не попадёт в k самых больших ни сейчас, ни потом: числа только приходят и никуда не деваются. Поэтому оно входит в кучу и тут же уходит, как 3 здесь.
  3. Куча не вырастает больше k + 1, поэтому каждый add стоит O(log k), сколько бы чисел ни пришло до него.

Сложность

init: время O(n log n) для n чисел. Каждый add: время O(log k), одно добавление и не больше одного удаления. Память O(k) после init: в куче k чисел.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.