Секретарь Проблема известная проблема описана как таким образом:
- Вам нужен новый секретарь
- У вас есть N кандидатов, с которыми вы можете взять интервью по одному
- Вы можете оценить каждого кандидата после собеседования. Ваша система подсчета очков никогда не даст двум претендентам одинаковый балл
- После собеседования с заявителем вы должны сразу дать «да» или «нет»
- Вы хотите заявителя с наивысшим баллом
Решение состоит в том, чтобы взять интервью у первых floor(N/e)
заявителей, а затем принять первого заявителя, который имеет более высокий балл, чем все предыдущие заявители. Если ни один из заявителей не выше, верните последнего заявителя. Интересно, что это дает лучшему заявителю 1/e
процент времени. e
относится к числу Эйлера . Чтобы получить значение e
, вы можете использовать встроенный код log
или жестко закодировать его как минимум до 5 десятичных знаков.
Входные данные:
Непустой массив уникальных целых неотрицательных чисел не больше 2^31-1
.
Выход:
Целое число, представляющее выбранного кандидата. Чтобы быть понятным, алгоритм:
- Найдите максимальный элемент в первых
floor(N/e)
элементах массива. - Выполните итерацию по оставшимся элементам и верните первый элемент, который превышает максимум, найденный на шаге 1.
- Если ни один из элементов не выше, чем вернуть последний элемент.
Например, скажем, ваш массив был [2,7,4,3,9,20]
, так N = 6
и floor(N/e) = 2
. Первые 2 элемента массива есть [2,7]
. Макс [2,7]
IS 7
. Остальные элементы есть [4,3,9,20]
. Первый элемент, который больше, чем 7
есть 9
, поэтому мы возвращаемся 9
.
Тестовые случаи:
[0] => 0
[100] => 100
[100, 45] => 100
[0, 1] => 0
[45, 100] => 45
[1, 4, 5] => 4
[1, 5, 4] => 5
[5, 4, 1] => 1
[5, 1, 4] => 4
[4, 1, 5] => 5
[56, 7, 37, 73, 90, 59, 65, 61, 29, 16, 47, 77, 60, 8, 1, 76, 36, 68, 34, 17, 23, 26, 12, 82, 52, 88, 45, 89, 94, 81, 3, 24, 43, 55, 38, 33, 15, 92, 79, 87, 14, 75, 41, 98, 31, 58, 53, 72, 39, 30, 2, 0, 49, 99, 28, 50, 80, 91, 83, 27, 64, 71, 93, 95, 11, 21, 6, 66, 51, 85, 48, 62, 22, 74, 69, 63, 86, 57, 97, 32, 84, 4, 18, 46, 20, 42, 25, 35, 9, 10, 19, 40, 54, 67, 70, 5, 44, 13, 78, 96]
=> 98
[10, 68, 52, 48, 81, 39, 85, 54, 3, 21, 31, 59, 28, 64, 42, 90, 79, 12, 63, 41, 58, 57, 13, 43, 74, 76, 94, 51, 99, 67, 49, 14, 6, 96, 18, 17, 32, 73, 56, 7, 16, 60, 61, 26, 86, 72, 20, 62, 4, 83, 15, 55, 70, 29, 23, 35, 77, 98, 92, 22, 38, 5, 50, 82, 1, 84, 93, 97, 65, 37, 45, 71, 25, 11, 19, 75, 78, 44, 46, 2, 53, 36, 0, 47, 88, 24, 80, 66, 87, 40, 69, 27, 9, 8, 91, 89, 34, 33, 95, 30]
=> 30
Ваше решение должно быть O(n)
, где n
длина массива. Если у вашего языка есть встроенная функция, которая находит максимум массива, вы можете предположить, что функция принимает O(n)
(и, надеюсь, это так).
Применяются стандартные лазейки, и это код-гольф , поэтому сделайте кратчайший ответ на своем любимом языке!
источник
e
следует использовать?e
(например, Python, гдеe=2.71828
корочеimport math;math.E
)Ответы:
Желе, 13 байт
Определенно алгоритм O (n) , надеюсь, реализация O (n) . Попробуйте онлайн!
Как это устроено
источник
CJam, 20 байт
Работает аналогично предложению Денниса.
источник
$W=
не работает в линейном времени.:e>
(уменьшите по максимуму)Джава,
128118 байтОтступ:
источник
MATL ,
272523 байтаИспользует тот же подход, что и ответ CJam А. Симмонса .
Попробуйте онлайн!
источник
JavaScript (ES6) 64
Меньше гольфа
Тестовое задание
источник
Рубин, 64 байта
источник
a.find
на втором шаге, хотя, очевидно, это намного менее эффективно.(0...c)
для диапазона, который исключает c.PARI / GP , 70 байт
Это может иметь проблемы с более старыми версиями gp при наличии синглтона, но это работает по крайней мере с версии 18487.
источник
JavaScript (ES6), 79 байт
Работает, потому что
findIndex
возвращает-1
при ошибке, ноa.slice(-1)[0]
возвращает последний элемент массива по желанию.источник
Python 2, 87 байт
Пользователь вводит массив в виде списка с квадратными скобками и запятыми. Python 2
input()
Команда здесь удобна.Независимо от того, прекращаем ли мы процесс раньше или нет, мы нанимаем последнего человека, который получил интервью.
источник
Perl 6, 43 байта
Я думаю, что это O (N)
источник
Python 3.5; 110 байт:
По сути, вышеприведенное делает то, что в первую очередь он принимает предоставленный массив «h», если он включает более 5 элементов (на данный момент ...), находит максимальное значение в первом (длина массива (len (h) )) / Число Эйлера (до 5 десятичных знаков)) элементов этого массива, а затем возвращает это значение как «k». Кроме того, «n» является максимальным значением в остальной части массива. Наконец, значение, возвращаемое функцией, является максимальным значением в массиве, содержащем как «k», так и «n».
Примечание:
max()
функция Python - O (n) сложность.Ниже приведена более читаемая версия кода, не относящаяся к коду для гольфа , с произвольным уникальным массивом из 10 элементов, подтверждающим его работоспособность:
источник