Next Permutation

Q: Wie hoch ist die Zeitkomplexität der nächsten Permutation?

O(n) . Ein Durchlauf von rechts findet den Drehpunkt, ein zweiter findet den Wert, mit dem getauscht werden soll, und eine Umkehrung korrigiert das Suffix. Der zusätzliche Speicherbedarf beträgt O(1) , da alles innerhalb des Arrays geschieht.

MittelArrays und Strings Zwei Zeiger

+10

Du erhältst ein Array aus Ganzzahlen nums, und Werte können mehrfach vorkommen. Stell dir alle unterschiedlichen Anordnungen dieser Werte in lexikografischer Reihenfolge vor: Vergleiche zwei Anordnungen an der ersten Stelle, an der sie sich unterscheiden; diejenige mit dem kleineren Wert an dieser Stelle kommt zuerst. Gib die Anordnung zurück, die in dieser Reihenfolge direkt nach nums kommt.

Wenn nums bereits die größte Anordnung ist, gibt es keine danach: Gib die kleinste zurück, bei der die Werte aufsteigend sortiert sind. Strebe eine Laufzeit von O(n) und einen zusätzlichen Speicherbedarf von O(1) an.

Funktion

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

numsinteger-array: die aktuelle Anordnung der Werte
Gibt zurückinteger-array: die nächste Anordnung in lexikografischer Reihenfolge oder die Werte in aufsteigender Reihenfolge sortiert, wenn nums die größte Anordnung ist

Einschränkungen

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 1000

Beispiele

Eingabe: nums = [2, 5, 4, 1]
Ausgabe: [4, 1, 2, 5]
Erklärung: Der Schwanz 5, 4, 1 fällt, also muss die 2 davor wachsen. Der kleinste Schwanzwert, der größer als 2 ist, ist 4; setze sie an diese Stelle und ordne den Rest aufsteigend: [4, 1, 2, 5].

Eingabe: nums = [3, 2, 2, 1]
Ausgabe: [1, 2, 2, 3]
Erklärung: Das gesamte Array fällt, also ist es die größte Anordnung von 3, 2, 2 und 1. Die Antwort springt zur kleinsten zurück: [1, 2, 2, 3].

Eingabe: nums = [1, 5, 1]
Ausgabe: [5, 1, 1]
Erklärung: Die erste 1 muss größer werden. Die letzte 1 ist gleich groß und nicht größer, daher kann nur der Wert 5 ihren Platz einnehmen. Das ergibt [5, 1, 1].

Weiterführende Frage

Wie würdest du stattdessen die vorherige Anordnung finden, also diejenige, die in der Wörterbuchreihenfolge direkt vor nums kommt?

Lösung

Ein fallendes Suffix ist bereits so groß, wie es seine Werte zulassen. Daher ändert die nächste Anordnung den Wert direkt davor, das Pivot-Element. Erhöhe das Pivot-Element um den kleinstmöglichen Betrag und mache dann das Suffix so klein wie möglich. Dafür braucht es zwei Durchläufe von rechts und eine Umkehrung innerhalb des Arrays.

Listenanordnungen der Reihe nach

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

Idee

Erzeuge Anordnungen aus den sortierten Werten tiefensuchend und probiere dabei immer zuerst den kleinsten noch unbenutzten Wert aus. Dadurch entstehen sie in lexikografischer Reihenfolge, sodass die erste Anordnung, die strikt größer als nums ist, die Antwort ist; falls es keine gibt, gib die sortierten Werte zurück. Wiederholte Werte erzeugen manche Anordnungen doppelt, wie bei 115, 151, 115, 151, 511, 511 für [1, 1, 5], aber eine Kopie wiederholt nur eine bereits erzeugte Anordnung, sodass die erste größere weiterhin die nächste ist.

Die Anzahl wächst wie n!: 12 verschiedene Werte ergeben 479,001,600 Anordnungen.

Algorithmus

Sortiere eine Kopie von nums in pool.
Erstelle Anordnungen nach dem Tiefensuchverfahren und wähle dabei unbenutzte Einträge von pool von links nach rechts aus.
Wenn eine Anordnung vollständig ist, vergleiche sie Position für Position mit nums.
Gib die erste Anordnung zurück, die größer als nums ist.
Wenn keine größer ist, gib pool zurück.

def nextPermutation(nums):
    n = len(nums)
    pool = sorted(nums)  # taking the smallest unused value first gives sorted order
    used = [False] * n
    current = []

    def build():
        # True once current holds the first arrangement greater than nums
        if len(current) == n:
            return current > nums  # Python compares lists in dictionary order
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(pool[i])
                if build():
                    return True
                current.pop()
                used[i] = False
        return False

    if build():
        return current
    return pool  # nothing is greater: nums was the largest arrangement

Finde das Pivot, vertausche und kehre das Suffix um

Idee

Der Drehpunkt ist der erste Wert von rechts, der kleiner ist als sein rechter Nachbar: die 2 in [2, 5, 4, 1]. Er ist die rechteste Position, die vergrößert werden kann, und eine Vergrößerung der rechtestmöglichen Position hält den Anstieg möglichst klein.

Vertausche den Drehpunkt mit dem kleinsten Suffixwert, der strikt größer ist. Das Suffix ist fallend, also ist das der rechteste Wert, der größer als der Drehpunkt ist: 4. Dadurch ergibt sich [4, 5, 2, 1]. Das Suffix ist weiterhin fallend, denn der alte Drehpunkt passt an die Stelle, an der 4 stand. Da der vordere Teil nun größer ist, sollte das Suffix so klein wie möglich sein und in aufsteigender Reihenfolge stehen. Das Umkehren einer fallenden Folge erreicht dies: [4, 1, 2, 5].

Gibt es keinen Drehpunkt, ist das Array die größte Anordnung; durch Umkehren des gesamten Arrays erhält man die kleinste. Jeder Schritt besteht aus einem Durchlauf oder einer Umkehrung: Zeitaufwand O(n) und Speicheraufwand O(1), wobei die R-Version eine Kopie der Größe O(n) zurückgibt.

Algorithmus

Setze i auf n-2 und bewege es nach links, solange nums[i] ≥ nums[i + 1] gilt.
Falls i ≥ 0 gilt, setze j auf n-1 und bewege es nach links, solange nums[j] ≤ nums[i] gilt, und vertausche dann nums[i] und nums[j].
Kehre den Abschnitt von i + 1 bis zum Ende um, indem du zwei Indizes aufeinander zu bewegst.
Gib nums zurück.

def nextPermutation(nums):
    n = len(nums)
    # 1. the pivot is the last index whose value is smaller than the next one
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2. swap it with the rightmost value that is larger than it
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 3. the suffix after the pivot is falling: reverse it to make it rising
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

Stolperfallen und Grenzfälle

Verwendung von > statt ≥ bei der Pivotsuche. In [3, 2, 2, 1] ist das Paar 2, 2 kein Anstieg, und dort anzuhalten wählt einen Pivot, der nicht vergrößert werden kann.
Vertauschen mit einem Wert, der dem Pivot entspricht. In [1, 5, 1] ändert das Vertauschen der beiden 1er nichts; suche nach einem Wert, der strikt größer ist.
Vertauschen mit dem größten Wert im Suffix. In [2, 5, 4, 1] bringt das die 5 nach vorn und überspringt alle Anordnungen, die mit 4 beginnen.
Den Fall ohne Pivot überspringen. Die größte Anordnung muss sortiert zurückgegeben werden, indem das gesamte Array umgekehrt wird.
In Rust löst ein usize-Index, der bei n-2 beginnt, eine Panic aus, wenn n = 1 gilt; auch das Weitergehen nach links über 0 hinaus löst eine Panic aus, wenn es keinen Pivot gibt. Verwende einen vorzeichenbehafteten Index oder zähle ab 1.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der nächsten Permutation?

O(n). Ein Durchlauf von rechts findet den Drehpunkt, ein zweiter findet den Wert, mit dem getauscht werden soll, und eine Umkehrung korrigiert das Suffix. Der zusätzliche Speicherbedarf beträgt O(1), da alles innerhalb des Arrays geschieht.

Warum kehrst du das Suffix um, anstatt es zu sortieren?

Nach dem Tausch ist das Suffix weiterhin absteigend sortiert, sodass seine Umkehrung es bereits aufsteigend sortiert. Eine Umkehrung benötigt O(n); eine Sortierung liefert dasselbe Ergebnis in O(n log n).

Funktioniert Next Permutation mit doppelten Werten?

Ja, solange beide Vergleiche gleiche Werte als nicht größer behandeln. Die Suche nach dem Drehpunkt überspringt gleiche Nachbarn mit ≥, und die Suche nach dem Tausch überspringt Werte, die dem Drehpunkt entsprechen, mit ≤. Dann wird aus [1, 5, 1] die nächste unterschiedliche Anordnung [5, 1, 1].

def nextPermutation(nums):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

nums = [2, 5, 4, 1]

Erwartete Ausgabe

[4, 1, 2, 5]