K-я порядковая статистика

Пусть дан массив $A$ длиной $N$ и пусть дано число $K$. Задача заключается в том, чтобы найти в этом массиве $K$-ое по величине число, т.е. $K$-ую порядковую статистику.

Давайте поймем, что в быстрой сортировке мы можем узнать, сколько элементов меньше данного, тогда рассмотрим три случая

1) количество чисел, меньше данного = $k - 1$, тогда наше число - ответ.

2) количество чисел, меньше данного >= $k$, тогда спускаемся рекурсивно в левую часть и ищем там ответ.

3) количество чисел, меньше данного < $k$, спускаемся в правую ищем ($k$ - левая - 1) - ое число.

За сколько же это работает, из быстрой сортировки мы имеем, что размер убывает приблизительно в 2 раза, тогда если мы просуммируем размеры массивов на каждом этапе, мы получим $\sum_{k=0}^n \frac{n}{2 ^ k} = O(n)$.

Также в с++ эта функция уже реализована :

1 nth_element(указатель на начало, указатель на нужный элемент, указатель на конец);

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin