Ist es möglich, die 2 größten Zahlen in einem Array zu finden und die Sammlung nur einmal durchzulaufen?
Ich hatte dies als eine Interviewfrage und habe es nicht rechtzeitig bekommen.
Es scheint ziemlich einfach ..
%Vor%Zum Beispiel:
%Vor%Schnelle Erklärung:
Im Allgemeinen können Sie die K größten (oder kleinsten) Zahlen in einem Array mit einem einzigen Durchgang für jedes K finden. Die gesamte Zeitkomplexität ist O (NK), wobei N die Größe des Arrays ist:
Behalten Sie eine sortierte Liste von Zahlen, die höchstens K Elemente enthält. Gehe durch das Array und für jeden Gegenstand:
Am Ende wird die Liste K größte Elemente enthalten, was wir wollten.
Diese Lösung ist jedoch ziemlich langsam. Unter Verwendung eines sich selbst ausbalancierenden binären Suchbaums oder einer Überspringungsliste könnten Sie zu O (N log K) gelangen. (Da es unmöglich ist, im allgemeinen Fall schneller als O (N log N) zu sortieren, und diese Methode kann verwendet werden, um das gesamte Array zu sortieren, wenn wir K = N setzen, sieht dies am besten aus.)
Im Fall von K = 2 brauchen Sie nicht all diese schweren Maschinen. Nur zwei Variablen, die die zwei Positionen in der Liste repräsentieren, sind genug.
Ja, ist es. Wenn Sie die Liste durchqueren, notieren Sie sich die größte gefundene Zahl, und wenn Sie eine größere Zahl gefunden haben, speichern Sie die größte gefundene Datei in einer zweitgrößten Datei, bevor Sie die größte gefundene Datei aktualisieren. Wenn der Wert größer als der zweitgrößte Wert ist, aktualisieren Sie den zweitgrößten Wert.