Find the Largest Number

Q: Wie hoch ist die Zeitkomplexität beim Finden des Maximums in einem Array?

Ein Durchlauf benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz. Keine Methode kann bei einem unsortierten Array effizienter sein, denn jedes Element, das du nie ausliest, könnte das größte sein. Das vorherige Sortieren kostet O(n log n) , was ohne Vorteil langsamer ist.

Q: Warum sollte das laufende Maximum beim ersten Element und nicht bei 0 beginnen?

Wenn jeder Wert negativ ist, ist keiner größer als 0 . Ein Maximum, das bei 0 beginnt, ändert sich also nie, und die Funktion gibt 0 zurück. Das erste Element ist immer ein echter Kandidat, daher ist es für jede Liste korrekt, dort zu beginnen. Auch die kleinste Ganzzahl deiner Sprache funktioniert, solange die Liste nie leer ist.

EinsteigerArrays und Strings

+10

Du erhältst eine nichtleere Liste von Ganzzahlen nums. Gib den größten Wert darin zurück. Die Werte können negativ sein, also kann auch die Antwort negativ sein. Finde ihn mit eigenen Vergleichen, ohne eine eingebaute Maximumfunktion wie max.

Funktion

findMax(nums: integer-array) → integer

numsinteger-array: die Liste der zu durchsuchenden Ganzzahlen
Gibt zurückinteger: der größte Wert in nums

Einschränkungen

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Beispiele

Eingabe: nums = [3, 17, 4, 12, 9]
Ausgabe: 17
Erklärung: Von links gelesen ist der größte Wert bisher 3, dann 17. Keine der Zahlen 4, 12 oder 9 ist größer als 17, also lautet die Antwort 17.

Eingabe: nums = [-8, -3, -11, -3]
Ausgabe: -3
Erklärung: Jeder Wert ist negativ, und -3 liegt am nächsten bei null, also ist er der größte. Er kommt zweimal vor, aber du gibst den Wert zurück, nicht seine Position.

+13 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du sowohl den größten als auch den kleinsten Wert mit etwa 3n/2 Vergleichen zurückgeben, statt 2n, indem du zuerst die Werte paarweise vergleichst?

Tipps

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

0 von 3 geöffnet

Lösung

Jeder Wert, den du überspringst, könnte der größte sein, daher liest jede Lösung jedes Element mindestens einmal. Die einzige tatsächliche Entscheidung ist, womit das laufende Maximum beginnt. Beginne mit dem ersten Element, niemals mit 0, denn jeder Wert in der Liste könnte negativ sein.

Eine Kopie sortieren und den letzten Wert nehmen

Idee

In einer von klein nach groß sortierten Liste steht der größte Wert am Ende. Kopiere nums, damit die Liste des Aufrufers unverändert bleibt, sortiere die Kopie und gib ihr letztes Element zurück. Bei [3, 17, 4, 12, 9] ist die sortierte Kopie [3, 4, 9, 12, 17], und das letzte Element ist 17.

Die Antwort ist richtig, aber das Sortieren erledigt weit mehr, als nötig ist. Es ordnet alle Werte, was etwa n log n Vergleiche erfordert, ungefähr 60,000 für n = 5000, obwohl du nur den größten Wert suchst. Auch die Kopie benötigt O(n) Speicher.

Übergib in JavaScript und TypeScript einen Komparator an sort. Ohne einen Komparator werden die Zahlen als Text verglichen, wodurch 12 und 17 vor 3 stehen.

Algorithmus

Kopiere nums.
Sortiere die Kopie vom kleinsten zum größten Wert und vergleiche dabei Zahlen als Zahlen.
Gib das letzte Element der sortierten Kopie zurück.

def findMax(nums):
    ordered = sorted(nums)  # a sorted copy, smallest first
    return ordered[-1]

Ein Durchlauf mit einem laufenden Maximum

Idee

Verwende eine Variable, largest, für den bisher größten gefundenen Wert. Setze sie auf nums[0], vergleiche sie mit jedem Wert und ersetze sie immer dann, wenn ein Wert größer ist. Wenn die Schleife endet, wurde largest mit jedem Element verglichen, also ist kein Wert in der Liste größer.

Bei [3, 17, 4, 12, 9] beginnt largest mit 3, wird zu 17 und bleibt bei 4, 12 und 9 unverändert 17. Das sind n-1 sinnvolle Vergleiche und eine zusätzliche Variable.

Der Start bei nums[0] sorgt dafür, dass auch Listen mit negativen Zahlen funktionieren. Beginne stattdessen bei 0, ist keiner der Werte in [-8, -3, -11, -3] größer, also gibst du 0 zurück – einen Wert, der gar nicht in der Liste vorkommt.

Algorithmus

Setze largest auf nums[0].
Durchlaufe jeden Wert x in nums.
Wenn x > largest gilt, setze largest auf x.
Gib nach der Schleife largest zurück.

def findMax(nums):
    largest = nums[0]  # never 0: every value may be negative
    for x in nums:
        if x > largest:
            largest = x
    return largest

Stolperfallen und Grenzfälle

Die Schleife ist kurz, daher liegen die Fehler darin, wo sie beginnt und was sie liest.

largest mit 0 oder -1 beginnen lassen. Jede Liste, deren Werte alle unter diesem Startwert liegen, gibt eine Zahl zurück, die nicht in der Liste steht.
Mit einer ausgedachten kleinen Zahl wie -1000000 beginnen. Die Werte hier reichen bis -10^9 hinunter, daher ist der Startwert immer noch größer. nums[0] erfordert keine Schätzung.
In Lua oder R nums[0] lesen, wo das erste Element nums[1] ist. Lua gibt nil zurück, und R gibt einen leeren Vektor zurück.
In einer Sprache mit nullbasierten Indizes eine Schleife mit i ≤ n ausführen, wodurch ein Element hinter dem Ende gelesen wird.
In JavaScript oder TypeScript ohne numerischen Comparator sortieren. Die lexikografische Reihenfolge von [3, 17, 4, 12, 9] endet mit 9, also gibst du 9 statt 17 zurück.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität beim Finden des Maximums in einem Array?

Ein Durchlauf benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz. Keine Methode kann bei einem unsortierten Array effizienter sein, denn jedes Element, das du nie ausliest, könnte das größte sein. Das vorherige Sortieren kostet O(n log n), was ohne Vorteil langsamer ist.

Wie findest du die größte Zahl in einem Array, ohne max zu verwenden?

Speichere das erste Element in einer Variablen. Durchlaufe die übrigen Elemente und speichere jeweils das Element stattdessen, wenn es größer als der Wert der Variablen ist. Am Ende der Schleife enthält die Variable den größten Wert.

Warum sollte das laufende Maximum beim ersten Element und nicht bei 0 beginnen?

Wenn jeder Wert negativ ist, ist keiner größer als 0. Ein Maximum, das bei 0 beginnt, ändert sich also nie, und die Funktion gibt 0 zurück. Das erste Element ist immer ein echter Kandidat, daher ist es für jede Liste korrekt, dort zu beginnen. Auch die kleinste Ganzzahl deiner Sprache funktioniert, solange die Liste nie leer ist.

Wann ist Sortieren eine gute Methode, um den größten Wert zu finden?

Wenn du mehr als nur den höchsten Wert benötigst, etwa die drei höchsten Werte oder den Median, und viele solcher Abfragen zur selben Liste stellen wirst. Für ein einzelnes Maximum ist ein Durchlauf schneller und lässt die Liste unverändert.

Python

def findMax(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [3, 17, 4, 12, 9]

Erwartet