Вычисление 90-го процентиля за время O (n)

Возможный дубликат:
может вы сортируете n целых чисел в O(n) амортизированной сложности?

Я должен написать алгоритм, который, учитывая несортированный список целых чисел, возвращает «наименьшее число в файле, которое превышает по крайней мере 90% чисел в файле» или -1, если такое число не существует. Достаточно просто: я сортирую список с помощью сортировки слиянием, затем начинаю с индекса на 90% пути и ищу, чтобы первое число было больше, чем число перед ним.

Однако вторая часть вопроса поставила меня в тупик. Нам дали дополнительную информацию: целые числа представляют зарплаты, то есть все они положительные, и подавляющее большинство из них меньше 1 000 000. По-видимому, с помощью этой дополнительной информации можно написать алгоритм, решающий исходную задачу за время O(n), но я не имею ни малейшего представления, как это возможно. Есть идеи?

Я бы опубликовал то, что я сделал до сих пор, но я не смог ничего придумать.


algorithm percentile
person GMA    schedule 12.11.2012    source источник
comment
Для этого можно использовать алгоритм выбора. Поищите в Кормене. Существуют также линейные алгоритмы сортировки по времени.   -  person The Unfun Cat    schedule 12.11.2012

Ответы (1)


arrow_upward
8
arrow_downward

Вы ищете алгоритм выбора, который выбирает k самый большой элемент в массиве. В статье Википедии приводится алгоритм O(n) для этого, который похож на быструю сортировку, но не сортирует весь массив и, таким образом, позволяет избежать времени выполнения O(n*logn).

Если все элементы ограничены определенным диапазоном (например, 1-1000000 в вашем случае), то другим подходом является их сортировка с использованием сортировка подсчетом или сортировка сегментами за O(n), а затем выберите нужный вам элемент. Поскольку в этом случае «подавляющее большинство» элементов меньше 1000000, а не все из них, вы можете выполнить сортировку ведра с 1000001 ведром и использовать последнее ведро для всех элементов выше 1000000.

person interjay    schedule 12.11.2012
comment
Для тех, кто не хочет читать статью в Википедии: алгоритм выбора на основе сравнения O(n) аналогичен быстрой сортировке, за исключением того, что после разделения массива вы повторяетесь только на той стороне, которая содержит индекс, который вы хотите выбрать. - person Alex D; 12.11.2012
comment
вы можете выполнить сортировку ведра с 1000001 ведром и использовать последнее ведро для всех элементов выше 1000000. Работает прелесть. Спасибо! - person GMA; 12.11.2012