Как найти k-й по величине элемент массива?

Три стандартных подхода: полная сортировка за `O(n log n)`, min-куча размера `k` за `O(n log k)` и Quickselect — в среднем `O(n)`, но `O(n²)` в худшем случае.

Min-куча размера k

• Держим k наибольших; если новый элемент больше вершины — заменяем вершину.
• O(n log k) времени, O(k) памяти, работает на потоке. В Python — heapq.nlargest(k, a)[-1].

Quickselect

• Как QuickSort, но рекурсия идёт только в ту часть, где лежит ответ: в среднем n + n/2 + n/4 + … ≈ 2n.
• Случайный pivot делает худший случай O(n²) маловероятным; median of medians гарантирует O(n), но с большой константой.
• В C++ это std::nth_element (introselect).

const kthLargest = (a, k) => { // k = 1 — максимум
  while (true) {
    const p = a[Math.floor(Math.random() * a.length)];
    const greater = a.filter((x) => x > p);
    const equal = a.filter((x) => x === p).length;
    if (k <= greater.length) {
      a = greater;
    } else if (k <= greater.length + equal) {
      return p;
    } else {
      k -= greater.length + equal;
      a = a.filter((x) => x < p);
    }
  }
};

Подводные камни

• Трёхпутевое разбиение нужно для дубликатов, иначе массив из одинаковых значений вырождается в O(n²).
• Путаница «k-й наибольший» и «k-й наименьший»: это n − k-й индекс при нумерации с нуля.

Коротко для собеседования

Для разовой задачи обычно берут Quickselect со случайным опорным элементом — в среднем O(n), а для потока или малого k — min-кучу размера k за O(n log k). Типичные ловушки — дубликаты без трёхпутевого разбиения и путаница между k-м наибольшим и k-м наименьшим.