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

In diesem Fall müssen Sie nur noch feststellen, ob es sich um (3) handelt. Wenn nicht, lautet die Antwort max(first, last).

In dem Fall, dass alle Elemente gleich sind, müssen Sie das Feld gründlich durchsuchen, um zu zeigen, dass es nicht irgendwo in der Mitte eine hohe Zahl gibt. Ich denke also, dass es O(n) ist, um festzustellen, ob man sich in (3) befindet.

Answer 2

Nun, von Fall zu Fall haben Sie

1. Die letzte Nummer.
2. Die erste Zahl.
3. Bewegen Sie sich vom Anfang zum Ende, halten Sie beim ersten Abstieg an und drucken Sie die vorherige Nummer aus.
4. Vergleichen Sie die erste und die letzte Nummer.

Wenn Sie nicht wissen, in welchem Fall Sie sich befinden, können Sie dies testen, während Sie den Maximalwert ermitteln, indem Sie Folgendes tun (in C-ähnlichem Pseudocode):

for (int i=0; i<end; ++i) {
    if (array[i] < array[i+1]) {
        // CASE 1 or 3
        for (int j=i+1; j<end; ++j) {
            if (array[j] > array[j+1]) {
                // CASE 3
                return array[j];
            }
         }
         // CASE 1
         return array[end];
     }
}
// CASE 2 or 4
return max(array[0],array[end]);

Answer 3

Sie können den Typ des Arrays bestimmen, indem Sie die ersten beiden und die letzten beiden Elemente untersuchen

1. Es ist das letzte Element
2. Es ist das erste Element
3. siehe unten
4. Es ist das größere der beiden Elemente

Für 3, beginnen Sie mit zwei Elementen in der Mitte des Feldes, wenn sie noch zunehmen, ist das Maximum höher im Feld, wenn sie abnehmen, ist das Maximum niedriger im Feld. Wiederholen Sie dies in einer binäre Suche Mode

Answer 4

Da die Fälle 1-3 alle einen Spitzenwert haben (Wert, der auf beiden Seiten von Werten umgeben ist, die niedriger sind als er selbst oder der Rand des Feldes), und Fall 4 zwei Spitzenwerte hat, die beide an den Enden des Feldes liegen, kann dieses Problem recht einfach gelöst werden durch O(log n) Zeit für alle Fälle:

Wenden Sie zunächst den 1D-Peak-Finding-Algorithmus an, um einen Peak in der Matrix zu finden.

Tritt der Spitzenwert in der Mitte des Feldes auf (nicht an der ersten oder letzten Position), handelt es sich um Fall Nr. 3, und der Spitzenwert ist auch das Maximum.

Wenn der Spitzenwert entweder das erste oder das letzte Element des Feldes ist, handelt es sich um einen der Fälle 1, 2 oder 4, und das Feld max ist max(first, last).

Python-ähnlicher Pseudocode:

def find-peak(list):
    mid=len(list)/2
    if (list[mid-1] > list[mid]:
        return find-peak(list[:mid-1])
    else if (list[mid+1] > list[mid]:
        return find-peak(list[mid+1:])
    else:
        return mid

def find-max(list):
    peak = find-peak(list)
    if peak==0 or peak==len(list)-1:
        return max(list[0], list[-1])
    else:
        return list[peak]

Answer 5

1.die letzte Zahl 2.die erste Zahl 3. Binäre Suche, Auswahl eines Pivots, Berechnung der Steigung, um zu entscheiden, ob die nächste Zahl nach links oder rechts gehen soll 4.erste oder letzte Zahl