Das Sekretärsproblem ist ein berühmtes Problem, das folgendermaßen beschrieben wird:

1. Du brauchst eine neue Sekretärin
2. Sie haben N Bewerber, die Sie einzeln befragen können
3. Sie können jeden Bewerber nach dem Vorstellungsgespräch bewerten. Ihr Punktesystem gibt niemals zwei Bewerbern die gleiche Punktzahl
4. Nachdem Sie einen Bewerber interviewt haben, müssen Sie sofort "Ja" oder "Nein" sagen
5. Sie möchten den Bewerber mit der höchsten Punktzahl

Die Lösung besteht darin, die ersten floor(N/e)Bewerber zu befragen und dann den ersten Bewerber zu akzeptieren, der eine höhere Punktzahl als alle vorherigen Bewerber aufweist. Wenn keiner der Bewerber höher ist, senden Sie den letzten Bewerber zurück. Interessanterweise hat der Top-Bewerber 1/ein dieser Zeit einen prozentualen Anteil. ebezieht sich auf Eulers Nummer . Um den Wert von zu erhalten e, können Sie einen eingebauten Wert verwenden logoder ihn mit mindestens 5 Dezimalstellen fest codieren .

Eingang:

Ein nicht leeres Array von eindeutigen nicht negativen ganzen Zahlen, nicht mehr als 2^31-1 .

Ausgabe:

Eine Ganzzahl, die den ausgewählten Kandidaten darstellt. Um klar zu sein, ist der Algorithmus:

1. Finden Sie das maximale Element in den ersten floor(N/e)Elementen des Arrays.
2. Durchlaufen Sie die verbleibenden Elemente und geben Sie das erste Element zurück, das höher als das in Schritt 1 festgelegte Maximum ist.
3. Wenn keines der Elemente höher ist, geben Sie das letzte Element zurück.

Angenommen, Ihr Array war [2,7,4,3,9,20], so N = 6und floor(N/e) = 2. Die ersten beiden Elemente des Arrays sind [2,7]. Das Maximum von [2,7]ist 7. Die restlichen Elemente sind [4,3,9,20]. Das erste Element , das größer ist als 7ist 9, so geht es zurück 9.

Testfälle:

[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

Ihre Lösung muss sein O(n), wo nist die Länge des Arrays. Wenn Ihre Sprache über eine integrierte Funktion verfügt, die das Maximum eines Arrays ermittelt, können Sie davon ausgehen, dass die Funktion dauertO(n) (und hoffentlich auch) dauert.

Es gelten Standardlücken, und dies ist ein Code-Golf , also machen Sie die kürzeste Antwort in Ihrer Lieblingssprache!

Gelee, 13 Bytes

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

Auf jeden Fall ein O (n) -Algorithmus, hoffentlich eine O (n) -Implementierung. Probieren Sie es online!

Wie es funktioniert

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 Bytes

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

Funktioniert ähnlich wie Dennis 'Vorschlag.

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 Bytes

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;}

Eingerückt:

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 Bytes

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

Verwendet den gleichen Ansatz wie A. Simmons 'CJam-Antwort .

Probieren Sie es 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)

Weniger golfen

(
 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
)

Prüfung

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>

Ruby, 64 Bytes

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

PARI / GP , 70 Bytes

Dies kann bei älteren Versionen von gp Probleme bereiten, wenn ein Singleton angegeben wird, funktioniert jedoch mindestens ab Revision 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 Byte

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

Funktioniert , weil findIndexkehrt -1bei einem Fehler, aber a.slice(-1)[0]kehrt das letzte Element der Anordnung , wie gewünscht.

Python 2, 87 Bytes

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

Der Benutzer gibt das Array als Liste mit eckigen Klammern und Kommas ein. Der input()Befehl von Python 2 ist hier praktisch.

Unabhängig davon, ob wir den Prozess vorzeitig beenden oder nicht, stellen wir die letzte Person ein, die interviewt wurde.

Perl 6, 43 Bytes

Ich denke das ist O (n)

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

Python 3.5; 110 Bytes:

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])

Grundsätzlich bedeutet das oben Gesagte, dass zuerst ein bereitgestelltes Array benötigt wird, "h" , solange es mehr als 5 Elemente enthält (vorerst ...), und der Maximalwert im ersten (Länge des Arrays (len (h )) / Eulers Zahl (bis zu 5 Dezimalstellen)) dieses Arrays und gibt diesen Wert als "k" zurück. Außerdem ist "n" der Maximalwert im Rest des Arrays. Schließlich ist der von der Funktion zurückgegebene Wert der Maximalwert in einem Array, das sowohl "k" als auch "n" enthält.

Hinweis: Die max()Funktion von Python ist die Komplexität von O (n).

Unten finden Sie eine besser lesbare Nicht-Code-Golf- Version des obigen Codes, die ein zufälliges, eindeutiges Array mit 10 Elementen enthält, um zu bestätigen, dass es funktioniert:

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))