Kth Largest Element in an Array

Значение, являющееся k-м по величине, определяется порядком сортировки, поэтому нужно получить этот порядок. При сортировке от наибольшего к наименьшему [7, 2, 9, 4, 9, 1]</code превращается в <code>[9, 9, 7, 4, 2, 1], а k-е по величине значение находится по индексу k-1. При k = 2 это индекс 1 — вторая 9. Если при сортировке наименьшее значение оказывается первым, вместо этого считывай значение по индексу n-k: значение с индексом 4 в [1, 2, 4, 7, 9, 9] — та же 9.

Дубликаты не требуют особой обработки: сортировка сохраняет все копии, и каждая копия занимает собственную позицию.

При n = 10^4 сортировка выполняет около n log n ≈ 1.3 × 10^5 сравнений, чего достаточно для прохождения всех тестов. Недостаток в том, что она упорядочивает все n значений, хотя важна только одна позиция. Следующие два подхода позволяют выполнить меньше этой работы.

Значение, занимающее k-е место по величине, — наименьшее среди k наибольших значений. Поэтому один раз пройдись по nums и сохраняй только k наибольших значений, встреченных к этому моменту, в мин-куче. Вершина мин-кучи — её наименьшее значение, и именно оно является возможным ответом.

Когда приходит значение x и в куче хранится меньше k значений, добавь его. В противном случае сравни x с вершиной. Если x не больше, то как минимум k сохранённых тобой значений не меньше x, поэтому x никогда не сможет стать ответом, и его можно пропустить. Если x больше, вершина больше не входит в k наибольших значений: замени её на x. В примере 2 при k = 4 первые четыре значения заполняют кучу значениями 5, -3, 8, 0, а вершиной становится -3. Затем 2 оказывается больше -3 и заменяет его, вершиной становится 0, а 0 и есть ответ.

Для каждого значения требуется не более одной операции с кучей, занимающей O(log k), поэтому общая сложность составляет O(n log k) по времени и O(k) по памяти. Это быстрее сортировки, когда k мало, и подходит для потока данных: тебе никогда не нужно хранить все значения одновременно. В Python есть heapq, в Java — PriorityQueue, в C++ — priority_queue с greater, в Go — container/heap, в Rust — BinaryHeap с Reverse, а в PHP — SplMinHeap. В коде для остальных языков куча реализована в массиве: дочерние узлы элемента с индексом i находятся по индексам 2i+1 и 2i+2, а в Lua и R, где отсчёт начинается с 1, — по индексам 2i и 2i+1.

Быстрая сортировка выбирает опорный элемент и разбивает массив на части: меньшие значения оказываются слева от него, большие — справа. После одного разбиения опорный элемент занимает своё окончательное место в отсортированном массиве, хотя ни одна из частей ещё не отсортирована. На этом основан алгоритм Quickselect. При порядке от меньшего к большему ответ находится по индексу target = n-k. После разбиения target находится либо слева от опорного элемента, либо на его месте, либо справа от него, поэтому продолжайте поиск только в одной части, а другую пропустите.

Для массива [7, 2, 9, 4, 9, 1] и k = 2 индекс target равен 6-2 = 4. Разобьём массив относительно 4: 2 и 1 занимают индексы 0 и 1, 4 — индекс 2, а 7, 9, 9 — индексы с 3 по 5. Индекс 4 находится справа, поэтому оставляем только индексы с 3 по 5. Разобьём эту часть относительно 9: 7 занимает индекс 3, а обе девятки — индексы 4 и 5. По индексу 4 находится 9, поэтому ответ — 9.

Используйте трёхстороннее разбиение: сначала значения меньше опорного элемента, затем равные ему значения, а после них — большие. Границы частей отслеживаются с помощью lt и gt. Блок равных значений [lt, gt] уже находится на своём месте в отсортированном массиве, поэтому, если target попадает в него, поиск завершён. При обычном двухстороннем разбиении массив из 10^4 копий числа 7 уменьшается на одно значение за проход — это около 5 × 10^7 шагов; трёхсторонний вариант находит ответ за один проход.

Выбирайте опорный элемент случайным образом. В половине случаев он попадает в среднюю половину диапазона, сокращая диапазон как минимум до трёх четвертей исходного размера, поэтому ожидаемое количество работы составляет несколько проходов по n значениям: O(n). В худшем случае сложность всё ещё составляет O(n²), если каждый опорный элемент оказывается крайним значением; фиксированный выбор, например первого элемента, приводит к этому на отсортированном массиве. Код работает с копией, для которой требуется O(n) памяти; если входные данные можно изменять, разбиение самого массива nums сокращает расход памяти до O(1).