Пусть A [0..n - 1] - массив различных целых чисел. Целое число с ранга k в A является k'th наибольшим целым числом из целых чисел в A. Медиана A является целым числом в A с рангом b (n - 1)/2c. Как может выглядеть алгоритм, который задает k, находит целое число с рангом k в A в Θ (n) времени?Предложение алгоритма поиска, который работает в Θ (n)?
Алгоритм, который вы ищите, называется QuickSelect. Это рандомизированный алгоритм и работает в ожидании O (n) время на массиве, состоящем из n элементов.
A worse-case O(n) algorithm также существует, но это только теоретический интерес.
Если вы можете поставить под угрозу время от Θ (n) до Θ (K * log (K)) - «K» означает K наибольшее целое число. Затем посмотрите вид MaxHeap. Когда «K» мало, он будет близок к Θ (n), но определенно будет больше при работе с медианным.
Что такое 'b' и' c'? – Max
Вероятно, вам нужна функция разделения quicksort. – IVlad