Kth Largest Element in an Array

Средняя№215k наибольших

Дан массив целых чисел и число k. Нужно вернуть k-е по величине число — то, что стояло бы k-м, если отсортировать массив от большего к меньшему. Повторы считаются, так что это не k-е из разных значений. Наш пример: [5, 9, 2, 9, 4, 7] и k = 3 — ответ 7, ведь две 9 занимают первое и второе места.

215 Kth Largest Element in an ArrayРазбор · 1×

Пример: [5, 9, 2, 9, 4, 7], k = 3. Сверху — числа; ниже — мин-куча, в которой 3 самых больших из прочитанных.

592947мин-кучаk = 3
ещё не прочитаноx, только что положилив кучекорень, сейчас уйдётубраноk-е по величине

В куче будут 3 самых больших из прочитанных чисел

01/23
сначала · назад · пуск · шаг
Скорость
1function findKthLargest(nums, k):
2 heap = empty min-heap
3 for each x in nums:
4 push x into heap
5 if size of heap > k:
6 pop min from heap
7 return min of heap
состояние
x
–
heap
[]
историянажмите шаг, чтобы вернуться

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

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

  1. После каждого шага в куче k самых больших из прочитанных чисел: как только их k + 1, уходит меньшее, а оно в k самых больших не входит.
  2. В конце в куче k самых больших чисел всего массива. Меньшее из них, корень, и есть k-е по величине.
  3. Каждая копия числа кладётся отдельно, поэтому две 9 занимают два места, и ответ 7 — как дала бы сортировка.

Сложность

Время O(n log k): n добавлений и не больше n удалений, каждое в куче не больше чем из k + 1 чисел. Память O(k) на кучу.

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

Решить на LeetCode ↗

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