Leaders in an Array

+10

Du erhältst ein Array aus ganzen Zahlen nums. Ein Element ist ein Anführer, wenn es größer oder gleich jedem Element rechts von ihm ist. Das letzte Element hat nichts rechts von sich und ist daher immer ein Anführer. Gib alle Anführer in der Reihenfolge zurück, in der sie in nums von links nach rechts erscheinen.

Funktion

leaders(nums: integer-array) → integer-array

numsinteger-array: das zu durchsuchende Integer-Array
Gibt zurückinteger-array: die führenden Elemente von nums, von links nach rechts

Einschränkungen

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

Beispiele

Eingabe: nums = [12, 5, 9, 3, 6, 2]
Ausgabe: [12, 9, 6, 2]
Erklärung: 2 steht zuletzt und führt daher. 6 schlägt die 2 dahinter, 9 schlägt 3, 6 und 2, und 12 schlägt alles. 5 verliert gegen 9 und 3 verliert gegen 6, also lautet die Antwort [12, 9, 6, 2].

Weiterführende Frage

Wenn die Werte einzeln eintreffen und du nach jedem Wert die bisherigen Spitzenreiter ausgeben musst, wie aktualisierst du die Liste in amortisiertem O(1)-Zeitaufwand pro Wert?

Tipps

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

0 von 3 geöffnet

Lösung

Lies von links nach rechts: Für jedes Element musst du sein Suffix neu durchsuchen. Gehe stattdessen von rechts nach links: Über das Suffix musst du nur seinen größten Wert kennen, und dafür genügt eine Variable. So wird aus einer Prüfung mit O(n²) ein einziger Durchlauf.

Überprüfe alles rechts

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Wende die Definition an: Scanne für jeden Index i die nachfolgenden Elemente und halte beim ersten an, das strikt größer als nums[i] ist. Wenn der Scan das Ende erreicht, ist nums[i] ein Anführer. Du testest die Indizes von links nach rechts, daher werden die Anführer der Reihe nach ausgegeben. In [12, 5, 9, 3, 6, 2] wird 5 bei 9 gestoppt und 3 bei 6.

Der Aufwand entsteht durch die Scans, die bis zum Ende laufen. Bei 24,999 gleichen Werten, gefolgt von einem größeren Wert, durchläuft jedes Element fast das gesamte Array: etwa 25,000 × 25,000 / 2, also über 3 × 10^8 Vergleiche.

Algorithmus

Erstelle eine leere Ergebnisliste.
Durchlaufe für jeden Index i die Indizes j von i + 1 bis zum Ende.
Wenn ein nums[j] größer als nums[i] ist, brich ab: nums[i] ist kein Leader.
Wenn kein solcher Index j existiert, füge nums[i] zum Ergebnis hinzu.
Gib das Ergebnis zurück.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

Ein Durchlauf von rechts mit einem laufenden Maximum

Idee

Mindestens so groß wie jedes Element rechts zu sein, ist dasselbe, wie mindestens so groß wie ihr Maximum zu sein. Wenn du von rechts nach links gehst, kannst du dieses Maximum laufend aktualisieren. Das letzte Element ist führend und setzt das Maximum. Jedes Element links davon ist führend, wenn es mindestens so groß wie das Maximum ist, und wird dann zum neuen Maximum; andernfalls befindet sich rechts davon ein größerer Wert.

Bei [12, 5, 9, 3, 6, 2]: 2 ist führend, dann 6, dann 9, dann 12, während 3 und 5 unter das Maximum fallen. Du hast [2, 6, 9, 12] gefunden; umgekehrt ist das die Antwort.

Jedes Element wird einmal verglichen: O(n) Zeit und O(1) zusätzlicher Speicherplatz neben dem Ergebnis. Die R-Version markiert die führenden Elemente in einem logical(n)-Vektor, daher beträgt ihr zusätzlicher Speicherplatz O(n).

Algorithmus

Füge das letzte Element zum Ergebnis hinzu und setze best auf dieses Element.
Gehe i vom vorletzten Index bis hinunter zu 0 durch.
Wenn nums[i] ≥ best gilt, füge nums[i] zum Ergebnis hinzu und setze best auf dieses Element.
Kehre das Ergebnis um, sodass die Leader von links nach rechts gelesen werden, und gib es zurück.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

Stolperfallen und Grenzfälle

> statt ≥ mit dem bisherigen Maximum vergleichen. In [4, 7, 7, 1, 7] ist jede 7 ein Anführer, aber ein strikter Vergleich behält nur die letzte bei.
Das Maximum auf 0 statt auf das letzte Element setzen. [-1, -5] muss beide zurückgeben, aber ein Maximum von 0 schließt sie aus.
Die Anführer in der Reihenfolge zurückgeben, in der du sie gefunden hast: [2, 6, 9, 12] statt [12, 9, 6, 2].
Das letzte Element zweimal hinzufügen, indem du die Schleife beim letzten Index startest, nachdem du es bereits zum Ergebnis hinzugefügt hast.
Jedes Element nur mit seinem Nachbarn vergleichen. In [5, 3, 9] ist 5 größer als die benachbarte 3, aber die 9 bedeutet, dass die Antwort [9] lautet.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität beim Finden von Anführern in einem Array?

O(n) bei einem einzigen Durchlauf von rechts, da jedes Element einmal mit dem laufenden Maximum verglichen wird. Jedes Element mit allen Elementen rechts davon zu vergleichen, kostet im ungünstigsten Fall O(n²), zum Beispiel, wenn alle Werte gleich sind.

Ist das letzte Element immer ein Anführer?

Ja. Ein führendes Element muss mindestens so groß sein wie jedes Element rechts von ihm. Das letzte Element hat keine Elemente rechts davon, daher ist die Bedingung erfüllt, ohne dass etwas überprüft werden muss.

Zählen gleiche Werte als Anführer?

Hier ja: Ein Anführer muss größer oder gleich jedem Element rechts von ihm sein, daher sind in [4, 7, 7, 1, 7] alle drei 7er Anführer. Bei manchen Versionen wird strikt größer verlangt; vergleiche dann mit >, und nur der letzte der gleichen Werte ist ein Anführer.

def leaders(nums):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

nums = [12, 5, 9, 3, 6, 2]

Erwartete Ausgabe

[12, 9, 6, 2]