Schreiben Sie eine Funktion, um Indizes der ersten beiden größten Zahlen zu finden

Question

So wurde ich gebeten, diese Frage während eines Online-Interviews zu lösen und schlug fehl. Ich wurde sofort abgelehnt. Ich versuche herauszufinden, was mit meinem Algorithmus falsch war.

zwei größten Zahlen

In der Programmiersprache Ihrer Wahl schreiben eine Funktion, die ein Array von ganzen Zahlen und gibt die Indizes der ersten beiden größten Zahlen nimmt. Dokumentieren Sie ein spezielles Verhalten in Randfällen, falls vorhanden. Die Funktion sollte eine Laufzeit von O(N) haben, wobei N die Länge des Arrays und O(1) zusätzlichen Speicherplatz ist.

ich diese Methode schrieb die Zahlen in C# sortieren:

int[] sortArrayIndicies(int[] numbers) 
{ 
    int high = int.MinValue; 
    int secondHigh = int.MinValue; 

    for(int i = 0; i < numbers.Length; i++) 
    { 
     if (numbers[i] > numbers[high]) 
     { 
     secondHigh = high; 
     high = i; 
     } 
     else if (numbers[i] > numbers[secondHigh]) 
     { 
     secondHigh = i; 
     } 
    } 

    return new[] {high, secondHigh}; 
} 

Wie für spezielles Verhalten für Grenzfälle zu dokumentieren, wurde I mit folgenden reagiert:

Die hohen und den zweiten Hohe Variablen wurden für den Fall, dass die Zahlen negativ sind, auf den Wert min int initialisiert, anstatt auf den Standardwert null. Komplexität ist O(N).

Wohin ging ich falsch? Ich weiß, dass die Komplexität der Zeit O(N) ist, weil ich durch die gesamte Liste iteriere, und die Komplexität des Raums ist O(1) wegen des kleinen (festen) Platzes für die hohen und zweiten hohen Variablen.

Answer 1

Der Kommentar ist eine indirekte Art zu sagen, dass Ihr Code für jede nicht leere Eingabe abstürzen wird, da numbers[high] während der ersten Iteration ein Äquivalent zur Referenzierung numbers[int.MinValue] sein wird.

Der Kommentar schlägt vor, dass Sie beide Werte auf 0 initialisieren. Ich denke du könntest weiter gehen und die Werte auf 0 und 1 oder auf 1 und 0 initialisieren, je nachdem, welche der beiden Anfangszahlen größer ist. Danach beginnen Sie mit der Iteration von Index 2. Natürlich müssen Sie sicherstellen, dass das Array mindestens zwei Elemente enthält.

Ein weiterer spezieller Fall, den Ihr Programm berücksichtigen sollte, ist, wenn zwei größte Zahlen einander gleich sind, wie in {1, 2, 5, 3, 4, 5, 4, 3}. In diesem Fall hätten sowohl high als auch secondHigh denselben Wert, daher sollte Ihr Programm {2, 5} zurückgeben.