O problema do secretário é um famoso problema descrito da seguinte maneira:
- Você precisa de uma nova secretária
- Você tem N candidatos que você pode entrevistar um de cada vez
- Você é capaz de pontuar cada candidato após a entrevista. Seu sistema de pontuação nunca dará a dois candidatos a mesma pontuação
- Depois de entrevistar um candidato, você deve dar um "sim" ou "não" imediato
- Você deseja que o candidato com a maior pontuação
A solução é entrevistar os primeiros floor(N/e)
candidatos e, em seguida, aceitar o primeiro candidato com uma pontuação mais alta do que todos os candidatos anteriores. Se nenhum dos candidatos for superior, retorne o último candidato. Curiosamente, isso fornece o 1/e
percentual mais alto de candidatos . e
refere-se ao número de Euler . Para obter o valor de e
, você pode usar um built-in,log
ou codificá-lo com pelo menos 5 pontos decimais.
Entrada:
Uma matriz não vazia de números inteiros não negativos únicos, no máximo 2^31-1
.
Resultado:
Um número inteiro representando o candidato escolhido. Para ser claro, o algoritmo é:
- Encontre o elemento máximo nos primeiros
floor(N/e)
elementos da matriz. - Itere pelos elementos restantes e retorne o primeiro elemento que é maior que o máximo encontrado na etapa 1.
- Se nenhum dos elementos for maior, retorne o último elemento.
Por exemplo, diga que sua matriz era [2,7,4,3,9,20]
, então N = 6
e floor(N/e) = 2
. Os 2 primeiros elementos da matriz são [2,7]
. O máximo de [2,7]
é 7
. Os elementos restantes são [4,3,9,20]
. O primeiro elemento que é maior que 7
é 9
, então retornamos 9
.
Casos de teste:
[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
Sua solução deve ser O(n)
, onde n
está o comprimento da matriz. Se seu idioma possui um valor interno que encontra o máximo de uma matriz, você pode assumir que a função aceita O(n)
(e espero que sim).
Aplicam-se brechas padrão, e este é um código de golfe , portanto, faça a resposta mais curta no seu idioma favorito!
fonte
e
deve ser usado?e
(por exemplo, Python, ondee=2.71828
é menor do queimport math;math.E
)Respostas:
Gelatina, 13 bytes
Definitivamente um algoritmo O (n) , espero que uma implementação O (n) . Experimente online!
Como funciona
fonte
CJam, 20 bytes
Funciona de maneira semelhante à sugestão de Dennis.
fonte
$W=
não é executado em tempo linear.:e>
(por reduzir máxima)Java,
128118 bytesRecuado:
fonte
MATL ,
272523 bytesUsa a mesma abordagem que a resposta CJam de A. Simmons .
Experimente online!
fonte
JavaScript (ES6) 64
Menos golfe
Teste
fonte
Ruby, 64 bytes
fonte
a.find
no segundo passo, embora obviamente seja muito menos eficiente.(0...c)
para um intervalo que exclua c.PARI / GP , 70 bytes
Isso pode ter problemas nas versões mais antigas do gp, quando fornecido um singleton, mas funciona pelo menos a partir da revisão 18487.
fonte
JavaScript (ES6), 79 bytes
Funciona porque
findIndex
retorna-1
com falha, masa.slice(-1)[0]
retorna o último elemento da matriz, conforme desejado.fonte
Python 2, 87 bytes
O usuário digita a matriz como uma lista, entre colchetes e vírgulas. Python 2's
input()
comando é conveniente aqui.Independentemente de encerrarmos o processo com antecedência, contratamos a última pessoa que foi entrevistada.
fonte
Perl 6, 43 bytes
Eu acho que isso é O (n)
fonte
Python 3.5; 110 bytes:
Basicamente, o que o acima faz é que, primeiramente, é necessária uma matriz fornecida, "h" , desde que inclua mais de 5 itens (por enquanto ...), encontre o valor máximo no primeiro (comprimento da matriz (len (h )) / Número de Euler (com 5 casas decimais)) itens dessa matriz e, em seguida, retorna esse valor como "k". Além disso, "n" é o valor máximo no restante da matriz. Finalmente, o valor retornado da função é o valor máximo em uma matriz que contém "k" e "n".
Nota: A
max()
função do Python é a complexidade O (n).Abaixo está uma versão mais legível e sem código de golfe do código acima que possui uma matriz aleatória e exclusiva de 10 itens, para confirmar que funciona:
fonte