Этот алгоритм работает при условии, что в массиве нет повторяющихся элементов.
Предварительная обработка
Найдите медианный элемент и поверните массив на этом элементе.Затем продолжайте применять эту процедуру к меньшей половине массива, пока не дойдете до одного элемента.
Вызывайте большую половину массивов на каждом шаге A (m), A (m-1), ...., A (0) для некоторого m.(0) всегда имеет размер 1, и каждый последующий массив либо удваивает размер предыдущего массива, либо плюс один.То есть len (A (0)) = 1, len (A (n)) = len (A (n-1)) или len (A (n-1)) + 1.Обратите внимание, что 2 ^ n <= len (A (n)) <2 ^ (n + 1). </p>
Нахождение медианы массива длины n занимает O (n) времени (с использованием хорошо известногоалгоритм поиска медианы линейного времени), а поворот также занимает O (n) времени.Вы применяете это рекурсивно (с меньшей стороны), что в целом занимает n + n / 2 + n / 4 + ... = O (n) времени.
Нахождение k'-го элемента
Определите S (n) как сумму длин A (0), A (1), ..., A (n-1).(S (0) = 0).
Найти n такое, что S (n) <= k и S (n + 1)> k.Вы можете сделать это за O (log k).
Затем найдите самый большой элемент kS (n) в A (n).Это можно сделать за время O (len (A (n))) с помощью (детерминированного варианта) алгоритма быстрого выбора.Поскольку len (A (n)) является тэтой (k), этот элемент был найден за время O (log k) + O (k) = O (k).
Примечание для понимания
Сначала легче рассмотреть случай, когда n - степень 2 минус 1. Тогда подмассивы A (i) удваиваются в размере.Например, когда n равно 16, а входными данными являются числа от 0 до 15 в некотором порядке, подмассивы могут выглядеть так:
A(0) = [0]
A(1) = [2, 1]
A(2) = [6, 3, 4, 5]
A(3) = [15, 8, 11, 10, 7, 12, 13, 9, 14]
Чтобы найти седьмой по величине элемент, мы находим, что он должен лежать в(2) и есть 3 элемента, объединенные в A (0) и A (1), поэтому нам нужно найти 7-3 = 4-й по величине элемент в A (2).Это мы делаем с помощью быстрого выбора.