The Sekretaris Masalah adalah masalah terkenal digambarkan sebagai demikian:

1. Anda membutuhkan sekretaris baru
2. Anda memiliki N pelamar yang dapat Anda wawancarai satu per satu
3. Anda dapat menilai setiap pelamar setelah wawancara. Sistem penilaian Anda tidak akan pernah memberi dua pelamar skor yang sama
4. Setelah Anda mewawancarai pelamar, Anda harus memberikan "ya" atau "tidak" langsung
5. Anda ingin pelamar dengan skor tertinggi

Solusinya adalah dengan mewawancarai floor(N/e)pelamar pertama , dan kemudian menerima pelamar pertama yang memiliki skor lebih tinggi dari semua pelamar sebelumnya. Jika tidak ada pelamar yang lebih tinggi, kembalikan pelamar terakhir. Cukup menarik, ini memberi pelamar 1/epersen atas waktu. emengacu pada nomor Euler . Untuk mendapatkan nilai e, Anda dapat menggunakan builtin,log ,, atau hardcode ke setidaknya 5 poin desimal.

Memasukkan:

Susunan bilangan bulat unik non-kosong tidak lebih dari 2^31-1 .

Keluaran:

Integer yang mewakili kandidat yang dipilih. Agar jelas algoritmanya adalah:

1. Temukan elemen maksimum di yang pertama floor(N/e) array.
2. Iterasi melalui elemen yang tersisa, dan kembalikan elemen pertama yang lebih tinggi dari maksimum yang ditemukan pada langkah 1.
3. Jika tidak ada elemen yang lebih tinggi, maka kembalikan elemen terakhir.

Sebagai contoh, katakan array Anda tadinya [2,7,4,3,9,20], begitu N = 6dan floor(N/e) = 2. 2 elemen pertama dari array adalah [2,7]. Maks [2,7]adalah 7. Elemen yang tersisa adalah [4,3,9,20]. Elemen pertama yang lebih besar dari 7itu 9, jadi kami kembali 9.

Kasus uji:

[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

Solusi Anda harus O(n), di mana npanjang array. Jika bahasa Anda memiliki builtin yang menemukan maksimum array, Anda dapat mengasumsikan bahwa fungsi tersebut diperlukanO(n) (dan mudah-mudahan itu terjadi).

Celah standar berlaku, dan ini adalah kode-golf , jadi buatlah jawaban tersingkat dalam bahasa favorit Anda!

Jelly, 13 byte

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

Jelas suatu algoritma O (n) , semoga implementasi O (n) . Cobalah online!

Bagaimana itu bekerja

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#=

Bekerja mirip dengan saran Dennis.

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 byte

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

Bertakuk:

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 byte

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

Menggunakan pendekatan yang sama dengan jawaban CJam A. Simmons .

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

Kurang golf

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

Uji

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 byte

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

PARI / GP , 70 byte

Ini mungkin mengalami masalah pada versi gp yang lebih lama ketika diberikan singleton, tetapi ia bekerja setidaknya dari revisi 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])

Bekerja karena findIndexmengembalikan -1pada kegagalan, tetapi a.slice(-1)[0]mengembalikan elemen terakhir dari array seperti yang diinginkan.

Python 2, 87 byte

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

Pengguna memasukkan array sebagai daftar, dengan tanda kurung dan koma. input()Perintah Python 2 nyaman di sini.

Terlepas dari apakah kami menghentikan proses lebih awal, kami mempekerjakan orang terakhir yang diwawancarai.

Perl 6, 43 byte

Saya pikir ini O (n)

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

Python 3.5; 110 byte:

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

Pada dasarnya, apa yang dilakukan di atas adalah bahwa ia pertama-tama membutuhkan array yang disediakan, "h" selama itu mencakup lebih dari 5 item (untuk saat ini ...), menemukan nilai maksimum dalam yang pertama (panjang array (len (h )) / Nomor Euler (ke 5 tempat desimal)) item dari array itu, dan kemudian mengembalikan nilai itu sebagai "k". Selain itu, "n" adalah nilai maksimum di seluruh array. Akhirnya, nilai yang dikembalikan dari fungsi adalah nilai maksimum dalam array yang mengandung "k" dan "n".

Catatan: max()Fungsi Python adalah O (n) kompleksitas.

Di bawah ini adalah lebih mudah dibaca, non-kode-golf versi kode di atas yang yang memiliki larik 10-item acak yang disediakan, untuk mengonfirmasi bahwa ia berfungsi:

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