Effizienter Weg zur Ermittlung der maximalen Anzahl in einem Array

Question

Dies ist eine Interviewfrage Es gibt ein Array mit ganzen Zahlen. Die Elemente in dem Array können den folgenden Mustern folgen.

1. die Nummern sind in aufsteigender Reihenfolge
2. die Nummern sind in absteigender Reihenfolge
3. die Zahlen steigen am Anfang und sinken am Ende
4. die Zahlen nehmen am Anfang ab und am Ende zu

Wie lässt sich die maximale Anzahl im Array effizient ermitteln?

Answer 1

Die Identifizierung der vier Fälle ist einfach, wenn wir davon ausgehen, dass die Sequenz keine sich wiederholende Nummer hat:

case 1: arr[0] < arr[1] && arr[end-1] < arr[end]
case 2: arr[0] > arr[1] && arr[end-1] > arr[end]
case 3: arr[0] < arr[1] && arr[end-1] > arr[end]
case 4: arr[0] > arr[1] && arr[end-1] < arr[end]

Wie bereits in anderen Antworten erwähnt, ist die Ermittlung des Höchstwerts ebenfalls sehr einfach:

case 1: arr[end]
case 2: arr[0]
case 3: binary search, until found n that arr[n-1] < arr[n] > arr[n+1]
case 4: max(arr[0],arr[end])

Answer 2

Die Antwort hängt davon ab, was mit "Effizienz" gemeint ist. Wenn Sie schnellen Code wollen, schauen Sie sich die Antwort eines anderen an. Wenn Sie als Programmierer effizient sein wollen, sollten Sie wahrscheinlich einfach einen Bibliotheksaufruf verwenden (wie max_element() in C++).

Answer 3

Dieses Problem erinnert mich an die Algorithmus des Goldenen Schnitts für die Suche nach dem Minimum einer unimodularen (d.h.: erst fallenden, dann steigenden) Funktion. Es handelt sich um eine Art verbesserte Version der binären Suche, die den Wert der Funktion (d. h.: das Array) in so wenigen Punkten wie möglich berechnet.

Jetzt muss man sie nur noch in eine diskrete Version übersetzen und ein paar Extras hinzufügen, um festzustellen, ob die Funktion konkav oder konvex ist.