Sekretarz Problem jest znanym problemem opisany jako sposób:
- Potrzebujesz nowej sekretarki
- Masz N kandydatów, z którymi możesz przesłuchać pojedynczo
- Jesteś w stanie ocenić każdego kandydata po rozmowie kwalifikacyjnej. Twój system punktacji nigdy nie da dwóm aplikantom tego samego wyniku
- Po przeprowadzeniu rozmowy z wnioskodawcą musisz natychmiast udzielić odpowiedzi „tak” lub „nie”
- Chcesz kandydata z najwyższym wynikiem
Rozwiązaniem jest przesłuchanie pierwszych floor(N/e)
wnioskodawców, a następnie zaakceptowanie pierwszego wnioskodawcy, który uzyskał wyższy wynik niż wszyscy poprzedni wnioskodawcy. Jeśli żaden z wnioskodawców nie jest wyższy, zwróć ostatniego wnioskodawcę. Co ciekawe, daje to pierwszemu wnioskodawcy 1/e
procent czasu. e
odnosi się do numeru Eulera . Aby uzyskać wartość e
, możesz użyć wbudowanego log
lub zakodować go z dokładnością do co najmniej 5 miejsc po przecinku.
Wejście:
Niepusta tablica unikalnych nieujemnych liczb całkowitych nie więcej niż 2^31-1
.
Wynik:
Liczba całkowita reprezentująca wybranego kandydata. Aby wyjaśnić, algorytm jest następujący:
- Znajdź maksymalny element w pierwszych
floor(N/e)
elementach tablicy. - Iteruj przez pozostałe elementy i zwróć pierwszy element, który jest wyższy niż maksimum znalezione w kroku 1.
- Jeśli żaden z elementów nie jest wyższy, zwróć ostatni element.
Powiedzmy, że twoja tablica była [2,7,4,3,9,20]
, więc N = 6
i floor(N/e) = 2
. Pierwsze 2 elementy tablicy to [2,7]
. Maksymalna [2,7]
to 7
. Pozostałe elementy to [4,3,9,20]
. Pierwszy element jest większy niż 7
jest 9
, więc wracamy 9
.
Przypadki testowe:
[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
Twoim rozwiązaniem musi być O(n)
, gdzie n
jest długość tablicy. Jeśli twój język ma wbudowaną funkcję, która wyszukuje maksimum tablicy, możesz założyć, że funkcja bierze O(n)
(i mam nadzieję, że tak).
Obowiązują standardowe luki, a to jest gra w golfa kodowego , więc stwórz najkrótszą odpowiedź w swoim ulubionym języku!
źródło
e
należy użyć?e
(np. Python, gdziee=2.71828
jest krótszy niżimport math;math.E
)Odpowiedzi:
Galaretka, 13 bajtów
Zdecydowanie algorytm O (n) , mam nadzieję, że implementacja O (n) . Wypróbuj online!
Jak to działa
źródło
CJam, 20 bajtów
Działa podobnie do sugestii Dennisa.
źródło
$W=
nie działa w czasie liniowym.:e>
(redukuj maksymalnie)Java,
128118 bajtówZębaty:
źródło
MATL ,
272523 bajtówUżywa tego samego podejścia, co odpowiedź CJam A. Simmonsa .
Wypróbuj online!
źródło
JavaScript (ES6) 64
Mniej golfa
Test
źródło
Rubinowy, 64 bajty
źródło
a.find
drugi krok, chociaż oczywiście jest to o wiele mniej wydajne.(0...c)
dla zakresu wykluczającego c.PARI / GP , 70 bajtów
Może to mieć problem ze starszymi wersjami gp, gdy ma się singleton, ale działa przynajmniej od wersji 18487.
źródło
JavaScript (ES6), 79 bajtów
Działa, ponieważ
findIndex
zwraca-1
w przypadku awarii, alea.slice(-1)[0]
zwraca ostatni element tablicy zgodnie z potrzebami.źródło
Python 2, 87 bajtów
Użytkownik wprowadza tablicę jako listę z nawiasami kwadratowymi i przecinkami.
input()
Polecenie Pythona 2 jest tutaj wygodne.Niezależnie od tego, czy zakończymy proces wcześniej, zatrudniamy ostatnią osobę, z którą przeprowadzono wywiad.
źródło
Perl 6, 43 bajtów
Myślę, że to O (n)
źródło
Python 3.5; 110 bajtów:
Zasadniczo powyższe działanie polega na tym, że najpierw pobiera podaną tablicę, „h”, o ile zawiera więcej niż 5 elementów (na razie ...), znajduje maksymalną wartość w pierwszej (długość tablicy (len (h )) / Liczba Eulera (do 5 miejsc po przecinku)) elementów tej tablicy, a następnie zwraca tę wartość jako „k”. Ponadto „n” jest wartością maksymalną w pozostałej części tablicy. Na koniec wartość zwracana z funkcji jest wartością maksymalną w tablicy zawierającej zarówno „k”, jak i „n”.
Uwaga:
max()
funkcją Pythona jest złożoność O (n).Poniżej znajduje się bardziej czytelna, niekodująca wersja golfowa powyższego kodu, która ma losową, unikalną tablicę 10-elementową, aby potwierdzić, że działa:
źródło