Sekretarz Problem jest znanym problemem opisany jako sposób:

1. Potrzebujesz nowej sekretarki
2. Masz N kandydatów, z którymi możesz przesłuchać pojedynczo
3. Jesteś w stanie ocenić każdego kandydata po rozmowie kwalifikacyjnej. Twój system punktacji nigdy nie da dwóm aplikantom tego samego wyniku
4. Po przeprowadzeniu rozmowy z wnioskodawcą musisz natychmiast udzielić odpowiedzi „tak” lub „nie”
5. 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/eprocent czasu. eodnosi się do numeru Eulera . Aby uzyskać wartość e, możesz użyć wbudowanego loglub 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:

1. Znajdź maksymalny element w pierwszych floor(N/e)elementach tablicy.
2. Iteruj przez pozostałe elementy i zwróć pierwszy element, który jest wyższy niż maksimum znalezione w kroku 1.
3. 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 = 6i 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ż 7jest 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 njest 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!

Galaretka, 13 bajtów

L:Øe³ḣȯ-Ṁ<i1ị

Zdecydowanie algorytm O (n) , mam nadzieję, że implementacja O (n) . Wypróbuj online!

Jak to działa

L:Øe³ḣȯ-Ṁ<i1ị  Main link. Argument: A (list of scores)

L              Get the length of A.
 :Øe           Divide the length by e, flooring the result.
    ³ḣ         Retrieve the that many scores from the beginning of A.
      ȯ-       Logical OR; replace an empty list with -1.
        Ṁ      Compute the maximum of those scores.
         <     Compare each score in A with that maximum.
          i1   Find the first index of 1 (0 if not found).
            ị  Retrieve the element of A at that index (the last one if 0).

CJam, 20 bajtów

q~___,1me/i<:e>f>1#=

Działa podobnie do sugestii Dennisa.

q~___                     Read array, duplicate three times
      ,                   Consume one to find the length
       1me/i              Push e then divide and take floor
            <             Take that many elements from the list
             :e>          Find maximum (Thanks to Dennis)
                f>        Label array elements larger than this as 1
                  1#      Find the first one (won't be in set of elements we've looked in)
                    =     Take that element from the final copy of the array. -1 gives us the last element as required

Java, 128 118 bajtów

a->{int c=(int)(a.length/Math.E),i=0,m=-1,t=0;for(;i<a.length;i++){t=a[i];if(i<c)m=t>m?t:m;if(t>m)return t;}return t;}

Zębaty:

static Function<Integer[], Integer> secretary2 = a -> {
    int c = (int) (a.length/Math.E),     // c = floor(N/E)
        i = 0, m = -1, t = 0;            // declare vars early to save bytes
    for (;i<a.length;i++) {              // for each element of input
        t = a[i];                        // cache element to save bytes
        if (i<c)                         // if before c
            m = t>m ? t : m;             // m = max(m, element)
        if (t>m)                         // if element > m
            return t;                    // return: we've found our best
    }                                    // if never found a good element
    return t;                            // return the last element
};

MATL , 27 25 23 bajtów

tttn1Ze/:)-1hX>>T0(f1))

Używa tego samego podejścia, co odpowiedź CJam A. Simmonsa .

Wypróbuj online!

JavaScript (ES6) 64

(a,l=a.length/Math.E,x)=>(a.every(v=>--l>0?x>v?1:x=v:(z=v)<x),z)

Mniej golfa

(
 a, 
 l=a.length/Math.E, // limit for stage 1
 x // init at undefined
)=>(
  a.every(v => --l > 0 // checking for >0 no need to floor
          ? x>v?1:x=v // stage 1, find max in x, always return truthy
          : (z=v)<x ) // stage 2, set z to current value and exit early if z>x
  , z // at last z has the last seen value
)

Test

f=(a,l=a.length/Math.E,x)=>(a.every(v=>--l>0?x>v?1:x=v:(z=v)<x),z)

console.log=x=>O.textContent+=x+'\n'

;[ 
 [0], [100], [0,1], [1,2,3],
 [100, 45],
 [45, 100],
 [1, 4, 5],
 [1, 5, 4],
 [5, 4, 1],
 [5, 1, 4],
 [4, 1, 5],   
 [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],
[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]
].forEach(t=>{
  var r=f(t)
  console.log(r+' : '+t)
})

<pre id=O></pre>

Rubinowy, 64 bajty

->a{m=a[0...c=a.size/Math::E].max
a[c..-1].find{|n|n>m}||a[-1]}

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.

v->m=vecmax(v[1..t=#v\exp(1)]);for(i=t+1,#v,v[i]>m&&return(v[i]));v[#v]

JavaScript (ES6), 79 bajtów

a=>(m=Math.max(...a.splice(0,a.length/Math.E)),a.slice(a.findIndex(x=>x>m))[0])

Działa, ponieważ findIndexzwraca -1w przypadku awarii, ale a.slice(-1)[0]zwraca ostatni element tablicy zgodnie z potrzebami.

Python 2, 87 bajtów

a=input()
t=int(len(a)/2.71828)
m=max(a[:t]+[-1])
for x in a[t:]:
 if x>m:break
print x

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.

Perl 6, 43 bajtów

Myślę, że to O (n)

{@^a.first(*>max @a[^floor @a/e])//@a[*-1]}

Python 3.5; 110 bajtów:

def Interview(h):k=max(h[0:int(len(h)/2.71828)-1]);n=max(h[int(len(h)/2.71828)-1:len(h)-1]);return max([k, n])

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:

import random, math

def Interview():
    k = max(h[0:int(len(h)/math.e)-1])
    n = max(h[int(len(h)/math.e)-1:len(h)-1])
    return max([k, n])

h = random.sample(range((2*31)-1), 10)

print(Interview(h))