|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Mike Roschin 2:5030/243 01 Feb 2002 19:57:01
To : Sergey Semenov
Subject : Hyжен алгоpитм
--------------------------------------------------------------------------------
щFrom Sergey Semenov (2:5030/1152.33) to All.
Ave Sergey Semenov!
SS> Hyжен быстpый алгоpитм поиска k-того минимального элемента в
SS> массиве длинной n. Разyмеется, O(n^2) не катит ;), хочется что-то
SS> типа O(nlogn) ...
IMHO можно так : рожаешь дополнительный массив на пять элементов, записываешь в
него первые пять элементов исходного массива. Последовательно, начиная с
шестого, берешь по одноу элементу из исходного массива, проверяешь нет ли в
дополнительном такого элемента, который больше взятого и если есть - замещаешь
его новым значением. Стало быть по окончании прогона в дополнительном у тебя
будет пятерка наименьших элементов из исходного массива. Выбрать из них
наибольший труда не составит :). Он и будет искомым.
Поскольку прогон вдоль искомого только один, то порядок получается O(n).
Куда уж быстрее :)
Have a fine CARRIER :) ! /White Thesis
--- FMailX32 1.60
* Origin: Слоны по деревьям не лазают! //Terminus-2 (2:5030/243)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
