Second Largest Number

+10

Du erhältst eine Liste von Ganzzahlen nums. Gib ihren zweitgrößten unterschiedlichen Wert zurück: den größten Wert, der strikt kleiner als das Maximum ist. Werte können mehrfach vorkommen, daher ist für [5, 5, 3] die Antwort 3 und nicht 5. Die Liste enthält immer mindestens zwei verschiedene Werte.

Funktion

secondLargest(nums: integer-array) → integer

numsinteger-array: die Liste von Ganzzahlen mit mindestens zwei unterschiedlichen Werten
Gibt zurückinteger: der größte Wert, der kleiner als das Maximum ist

Einschränkungen

2 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums enthält mindestens zwei unterschiedliche Werte.

Beispiele

Eingabe: nums = [4, 9, 2, 7, 9]
Ausgabe: 7
Erklärung: Das Maximum ist 9. Es kommt zweimal vor, aber eine zweite Kopie des Maximums zählt nicht, daher ist die Antwort der nächstniedrigere Wert, 7.

Eingabe: nums = [-5, -1, -8]
Ausgabe: -5
Erklärung: Von der größten zur kleinsten Zahl sind die Werte -1, -5, -8. Die zweitgrößte Zahl ist -5, obwohl sie negativ ist.

Eingabe: nums = [6, 6, 6, 3]
Ausgabe: 3
Erklärung: Es gibt nur zwei unterschiedliche Werte: 6 und 3. Wie oft sich 6 auch wiederholt, der zweitgrößte Wert ist 3.

Weiterführende Frage

Kannst du den drittgrößten unterschiedlichen Wert in einem Durchlauf mit drei Variablen und ohne Sortieren zurückgeben?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Zwei Details machen dies schwieriger als das Finden des Maximums. Das Maximum kann mehrfach vorkommen, und ein wiederholtes Maximum darf nicht als zweitgrößter Wert ausgegeben werden. Die Antwort kann negativ sein, daher liefert eine Variable, die mit 0 beginnt, bei einer Liste, die nur negative Werte enthält, ein falsches Ergebnis. Wenn du die beiden größten unterschiedlichen Werte in einem Durchlauf mit strikten Vergleichen ermittelst, werden beide Probleme gelöst.

Sortieren und über das Maximum hinaus herunterzählen

Idee

Sortiere eine Kopie von klein nach groß. Das Maximum steht am Ende, möglicherweise mehrmals hintereinander. Gehe vom Ende aus nach links über alle Vorkommen des Maximums hinweg; der erste andere Wert ist der zweitgrößte. Für [6, 6, 6, 3] ist die sortierte Kopie [3, 6, 6, 6]: Du überspringst drei 6en und landest bei 3.

Hier das vorletzte Element zurückzugeben, ist der klassische Fehler. Für [4, 9, 2, 7, 9] gibt das erneut 9 zurück, also wieder das Maximum. Der Durchlauf kann nicht über den Anfang hinausgehen, denn die Liste enthält mindestens zwei unterschiedliche Werte.

Die Antwort ist richtig, aber beim Sortieren werden alle Werte geordnet, obwohl dich nur die beiden größten interessieren. Das kostet O(n log n) Zeit und die Kopie O(n) Speicher.

Algorithmus

Kopiere nums und sortiere die Kopie von klein nach groß.
Setze einen Index i auf die letzte Position.
Solange der Wert an i dem Maximum entspricht, bewege i einen Schritt nach links.
Gib den Wert an i zurück.

def secondLargest(nums):
    ordered = sorted(nums)
    i = len(ordered) - 1
    # Step left past every copy of the maximum.
    while ordered[i] == ordered[-1]:
        i -= 1
    return ordered[i]

Zwei Durchläufe

Idee

Teile die Aufgabe in zwei Durchgänge auf. Im ersten Durchgang wird das Maximum ermittelt, wie bei „Die größte Zahl finden“. Im zweiten Durchgang wird nach dem größten Wert gesucht, der strikt kleiner als dieses Maximum ist. Bei [4, 9, 2, 7, 9] findet der erste Durchgang 9, und der zweite überspringt beide 9 und behält den größten Wert aus 4, 2 und 7 bei, nämlich 7.

Initialisiere second mit einem Wert, der unter allen Werten liegt, die die Liste enthalten kann, beispielsweise der kleinsten Ganzzahl, die deine Sprache darstellen kann. Die Liste enthält mindestens zwei verschiedene Werte, daher ist ein Wert kleiner als das Maximum und ersetzt diesen Startwert immer.

Jeder Durchgang ermittelt ein laufendes Maximum, sodass der Gesamtaufwand O(n) Zeit und O(1) Speicherplatz beträgt. Der Nachteil ist, dass die Liste zweimal durchlaufen werden muss. Das ist unmöglich, wenn die Werte einzeln eintreffen und nach dem Lesen nicht mehr verfügbar sind.

Algorithmus

Durchlaufe nums einmal und speichere das Maximum in largest.
Setze second auf einen Wert unterhalb aller zulässigen Werte.
Durchlaufe die Liste erneut. Setze für jedes x mit x < largest und x > second second auf x.
Gib second zurück.

def secondLargest(nums):
    largest = nums[0]
    for x in nums:
        if x > largest:
            largest = x
    second = float("-inf")  # below every allowed value
    for x in nums:
        if x < largest and x > second:
            second = x
    return second

Ein Durchlauf zur Ermittlung der beiden größten Werte

Idee

Behalte zwei Variablen, largest und second, für die beiden größten unterschiedlichen Werte, die bisher gesehen wurden. Jeder neue Wert x fällt in einen von drei Fällen. Wenn x größer als largest ist, rückt das bisherige largest auf den zweiten Platz, und x übernimmt den ersten Platz. Liegt x strikt zwischen second und largest, wird es zum neuen second. In allen anderen Fällen ändert sich nichts.

Die strikten Vergleiche sorgen dafür, dass Duplikate richtig behandelt werden. Für [4, 9, 2, 7, 9]: largest wird zuerst zu 4, dann zu 9, wobei second = 4 gilt. 2 ändert nichts, 7 liegt zwischen 4 und 9, also gilt second = 7, und die letzte 9 ist gleich largest und wird daher übersprungen. Die Antwort ist 7.

Initialisiere beide Variablen mit Werten, die kleiner als jeder mögliche Wert sind. Wenn Du beide mit 0 initialisierst, wird für [-5, -1, -8] 0 zurückgegeben, weil kein Wert jemals größer als 0 ist. Da die Liste zwei unterschiedliche Werte enthält, endet second immer mit einem tatsächlichen Wert aus der Liste.

Algorithmus

Setze largest und second auf Werte unterhalb jedes zulässigen Werts.
Durchlaufe jeden Wert x in nums.
Wenn x > largest gilt, verschiebe largest nach second und setze largest auf x.
Andernfalls, wenn x < largest und x > second gilt, setze second auf x.
Gib nach der Schleife second zurück.

def secondLargest(nums):
    # Both start below every allowed value.
    largest = second = float("-inf")
    for x in nums:
        if x > largest:
            second = largest  # the old maximum drops to second place
            largest = x
        elif largest > x > second:
            second = x
    return second

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen durch Duplikate des Maximums oder durch negative Werte.

Das vorletzte Element der sortierten Liste zurückgeben. Bei einem wiederholten Maximum, wie in [4, 9, 2, 7, 9], ist das wieder das Maximum.
Die Variablen auf 0 setzen. Bei [-5, -1, -8] ist kein Wert größer als 0, und du gibst 0 zurück – eine Zahl, die nicht in der Liste vorkommt.
Im ersten Fall x >= largest schreiben. Eine zweite 9 verschiebt dann die erste 9 nach second, und du gibst 9 zurück.
second nur aktualisieren, wenn ein neues Maximum erscheint. In [10, 20, 15] wird die 15 nie in second übernommen, und du gibst 10 zurück.
Duplikate mit einer Menge entfernen und anschließend sortieren. Das funktioniert, benötigt aber O(n) Speicher und O(n log n) Zeit für eine Aufgabe, die sich mit einem einzigen Durchlauf erledigen lässt.

Häufige Fragen3

Wie findest du in einem Durchlauf die zweitgrößte Zahl in einem Array?

Behalte den größten und den zweitgrößten unterschiedlichen Wert, die bisher gesehen wurden. Wenn ein Wert den größten übertrifft, rückt der bisherige größte auf den zweiten Platz. Liegt ein Wert strikt zwischen den beiden, ersetzt er den zweitgrößten. Nach einem Durchlauf enthält die Variable für den zweitgrößten Wert die Antwort.

Wie hoch ist die Zeitkomplexität beim Finden des zweitgrößten Elements?

Die Methoden mit einem und zwei Durchläufen benötigen beide O(n) Zeit und O(1) zusätzlichen Speicherplatz. Zuerst zu sortieren benötigt O(n log n) Zeit. O(n) lässt sich nicht unterschreiten, da jeder Wert mindestens einmal gelesen werden muss.

Wie wirken sich Duplikate auf das zweitgrößte Element aus?

Bei dieser Aufgabe wird nach dem zweitgrößten unterschiedlichen Wert gefragt, daher werden Kopien des Maximums übersprungen. Für [9, 9, 7] lautet die Antwort 7. Bei manchen Versionen der Aufgabe werden stattdessen Positionen gezählt, und die Antwort wäre 9. Prüfe also vor dem Programmieren, was gemeint ist.

def secondLargest(nums):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

nums = [4, 9, 2, 7, 9]

Erwartete Ausgabe

Second Largest Number

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Sortieren und über das Maximum hinaus herunterzählen

Zwei Durchläufe

Ein Durchlauf zur Ermittlung der beiden größten Werte

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben