El problema del secretario es un famoso problema descrito de la siguiente manera:
- Necesitas una nueva secretaria
- Tienes N solicitantes que puedes entrevistar uno a la vez
- Puede calificar a cada solicitante después de la entrevista. Su sistema de puntaje nunca le dará a dos solicitantes el mismo puntaje
- Después de entrevistar a un solicitante, debe dar un "sí" o un "no" inmediatos.
- Quieres al solicitante con la puntuación más alta
La solución es entrevistar a los primeros floor(N/e)
solicitantes y luego aceptar al primer solicitante que tenga una puntuación más alta que todos los solicitantes anteriores. Si ninguno de los solicitantes es superior, devuelva el último solicitante. Curiosamente, esto le da al solicitante principal el 1/e
porcentaje del tiempo. e
se refiere al número de Euler . Para obtener el valor de e
, puede usar un código incorporado log
o codificarlo con al menos 5 puntos decimales.
Entrada:
Una matriz no vacía de enteros únicos no negativos no más de 2^31-1
.
Salida:
Un entero que representa al candidato elegido. Para ser claros, el algoritmo es:
- Encuentre el elemento máximo en los primeros
floor(N/e)
elementos de la matriz. - Itere a través de los elementos restantes y devuelva el primer elemento que sea más alto que el máximo encontrado en el paso 1.
- Si ninguno de los elementos es más alto, devuelva el último elemento.
Por ejemplo, digamos que su matriz era [2,7,4,3,9,20]
, así N = 6
y floor(N/e) = 2
. Los primeros 2 elementos de la matriz son [2,7]
. El máximo de [2,7]
es 7
. Los elementos restantes son [4,3,9,20]
. El primer elemento que es mayor que 7
es 9
, entonces volvemos 9
.
Casos de prueba:
[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
Su solución debe ser O(n)
dónde n
está la longitud de la matriz. Si su idioma tiene una función incorporada que encuentra el máximo de una matriz, puede suponer que la función toma O(n)
(y es de esperar que lo haga).
Se aplican las lagunas estándar, y este es un código de golf , ¡así que haga la respuesta más corta en su idioma favorito!
fuente
e
debe usar?e
(por ejemplo, Python, dondee=2.71828
es más corto queimport math;math.E
)Respuestas:
Jalea, 13 bytes
Definitivamente un algoritmo O (n) , con suerte una implementación O (n) . Pruébalo en línea!
Cómo funciona
fuente
CJam, 20 bytes
Funciona de manera similar a la sugerencia de Dennis.
fuente
$W=
no se ejecuta en tiempo lineal.:e>
(Reducir al máximo)Java,
128118 bytesSangrado:
fuente
MATL ,
272523 bytesUtiliza el mismo enfoque que la respuesta CJam de A. Simmons .
Pruébalo en línea!
fuente
JavaScript (ES6) 64
Menos golf
Prueba
fuente
Ruby, 64 bytes
fuente
a.find
en el segundo paso, aunque obviamente es mucho menos eficiente.(0...c)
para un rango que excluya c.PARI / GP , 70 bytes
Esto puede tener problemas en versiones anteriores de gp cuando se le da un singleton, pero funciona al menos desde la revisión 18487.
fuente
JavaScript (ES6), 79 bytes
Funciona porque
findIndex
regresa-1
en caso de falla, peroa.slice(-1)[0]
devuelve el último elemento de la matriz como se desee.fuente
Python 2, 87 bytes
El usuario ingresa a la matriz como una lista, con corchetes y comas. Python 2
input()
comando de es conveniente aquí.Ya sea que terminemos o no el proceso temprano, contratamos a la última persona que fue entrevistada.
fuente
Perl 6, 43 bytes
Creo que esto es O (n)
fuente
Python 3.5; 110 bytes:
Básicamente, lo que hace lo anterior es que primero toma una matriz proporcionada, "h" , siempre que incluya más de 5 elementos (por ahora ...), encuentra el valor máximo en la primera (longitud de la matriz (len (h )) / Número de Euler (a 5 decimales)) elementos de esa matriz y luego devuelve ese valor como "k". Además, "n" es el valor máximo en el resto de la matriz. Finalmente, el valor devuelto por la función es el valor máximo en una matriz que contiene "k" y "n".
Nota: La
max()
función de Python es complejidad O (n).A continuación se muestra una versión más legible, sin código de golf del código anterior que tiene una matriz aleatoria y única de 10 elementos, para confirmar que funciona:
fuente