Second Largest Number
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
- 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-109 ≤ nums[i] ≤ 109numsenthä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:
6und3. Wie oft sich6auch wiederholt, der zweitgrößte Wert ist3.
+15 versteckte Tests beim Einreichen
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.
Um das Maximum zu finden, brauchst du eine Variable. Woran könntest du dich mit einer zweiten Variable erinnern, während du die Liste durchgehst?
Verfolge den größten und den zweitgrößten unterschiedlichen Wert. Ein neuer Wert kann den größten übertreffen, strikt zwischen den beiden liegen oder nichts ändern.
Setze beide Variablen zunächst auf einen Wert unterhalb jedes zulässigen Werts. Wenn
x > largestgilt, verschiebelargestnachsecondund speicherex. Andernfalls speicherexinsecond, wenn es strikt zwischen den beiden liegt.
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
numsund sortiere die Kopie von klein nach groß. - Setze einen Index
iauf die letzte Position. - Solange der Wert an
idem Maximum entspricht, bewegeieinen Schritt nach links. - Gib den Wert an
izurü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
numseinmal und speichere das Maximum inlargest. - Setze
secondauf einen Wert unterhalb aller zulässigen Werte. - Durchlaufe die Liste erneut. Setze für jedes
xmitx < largestundx > secondsecondaufx. - Gib
secondzurü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 secondEin 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
largestundsecondauf Werte unterhalb jedes zulässigen Werts. - Durchlaufe jeden Wert
xinnums. - Wenn
x > largestgilt, verschiebelargestnachsecondund setzelargestaufx. - Andernfalls, wenn
x < largestundx > secondgilt, setzesecondaufx. - Gib nach der Schleife
secondzurü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
0setzen. Bei[-5, -1, -8]ist kein Wert größer als0, und du gibst0zurück – eine Zahl, die nicht in der Liste vorkommt. - Im ersten Fall
x >= largestschreiben. Eine zweite9verschiebt dann die erste9nachsecond, und du gibst9zurück. secondnur aktualisieren, wenn ein neues Maximum erscheint. In[10, 20, 15]wird die15nie insecondübernommen, und du gibst10zurück.- Duplikate mit einer Menge entfernen und anschließend sortieren. Das funktioniert, benötigt aber
O(n)Speicher undO(n log n)Zeit für eine Aufgabe, die sich mit einem einzigen Durchlauf erledigen lässt.
Häufige Fragen4
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.
Was solltest du zurückgeben, wenn es keinen zweitgrößten Wert gibt?
Hier kann das nicht passieren: Die Liste enthält immer zwei unterschiedliche Werte. Allgemein hat eine Liste wie [4, 4, 4] keine Lösung, und du würdest einen Platzhalter wie -1 oder null zurückgeben oder einen Fehler auslösen. Du kannst den Fall erkennen, wenn second nach der Schleife noch immer seinen Anfangswert enthält.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def secondLargest(nums):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
nums = [4, 9, 2, 7, 9]
Erwartet
7