Count Inversions

Q: Was ist eine Inversion in einem Array?

Eine Inversion ist ein Paar von Positionen i < j , bei dem nums[i] > nums[j] gilt, sodass ein größerer Wert vor einem kleineren steht. Eine sortierte Liste hat 0 Inversionen, und eine umgekehrte Liste mit unterschiedlichen Werten hat die größtmögliche Anzahl, n(n-1)/2 . Die Anzahl entspricht der Zahl der benachbarten Vertauschungen, die Bubble Sort durchführt.

Q: Wie hoch ist die Zeitkomplexität beim Zählen von Inversionen mit Merge Sort?

O(n log n) Laufzeit und O(n) zusätzlicher Speicherplatz für den Merge-Puffer. Jede der log n Mischebenen berührt jeden Wert einmal, also etwa 3 × 10^5 Schritte für 2 × 10^4 Werte. Die Schleife, die die Paare einzeln verarbeitet, hat eine Laufzeit von O(n²) .

MittelSortieren Rekursion

+10

Gegeben sei eine Liste von Ganzzahlen nums. Gib die Anzahl der Inversionen zurück: Paare von Indizes i < j, für die nums[i] > nums[j] gilt, also ein größerer Wert vor einem kleineren steht. Gleiche Werte bilden niemals eine Inversion, und eine sortierte Liste enthält keine.

Funktion

countInversions(nums: integer-array) → integer

numsinteger-array: die Liste der Ganzzahlen
Gibt zurückinteger: die Anzahl der Paare i < j, für die nums[i] > nums[j] gilt

Einschränkungen

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Die Antwort beträgt höchstens n(n-1)/2 < 2 × 10⁸, daher passt sie in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiele

Eingabe: nums = [5, 3, 8, 1, 4]
Ausgabe: 6
Erklärung: 5 steht vor 3, 1 und 4: 3 Paare. 3 steht vor 1 und 8 vor 1 und 4: 3 weitere. 1 und 4 sind in der richtigen Reihenfolge, also beträgt die Gesamtzahl 6.

Weiterführende Frage

Was ändert sich, wenn ein Paar nur dann zählt, wenn nums[i] > 2 × nums[j]? Kann Merge-Sort solche Paare weiterhin in O(n log n) zählen?

Lösung

Das Überprüfen jedes Paares erfordert etwa n² / 2 Vergleiche. Merge Sort zählt Paare in Gruppen: Wenn während des Zusammenführens ein Wert aus der rechten Hälfte eingefügt wird, ist jeder noch wartende Wert aus der linken Hälfte größer und kam davor. Eine Subtraktion zählt die ganze Gruppe, sodass das Zählen über die Sortierung in O(n log n) hinaus nichts kostet.

Überprüfe jedes Paar

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

Idee

Prüfe für jeden Index i jeden späteren Index j und addiere 1, wenn nums[i] > nums[j] gilt. Das ist die Definition, und durch den strikten Vergleich werden gleiche Werte nicht berücksichtigt.

Der Aufwand beträgt n(n-1)/2 Vergleiche: bei 2 × 10^4 Werten fast 2 × 10^8, und eine Verdopplung von n vervierfacht den Aufwand.

Algorithmus

Setze count = 0.
Für jedes i von 0 bis n-1 und jedes j von i + 1 bis n-1 addiere 1 zu count, wenn nums[i] > nums[j].
Gib count zurück.

def countInversions(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] > nums[j]:
                count += 1
    return count

Merge-Sort, der beim Zusammenführen zählt

Idee

Teile die Liste in der Mitte. Eine Inversion hat beide Werte in der linken Hälfte, beide in der rechten Hälfte oder je einen auf jeder Seite. Durch rekursives Vorgehen in jeder Hälfte werden die ersten beiden Arten gezählt und die jeweilige Hälfte sortiert. Beim Sortieren werden Werte nur innerhalb einer Hälfte verschoben, sodass jeder linke Wert weiterhin vor jedem rechten Wert steht und die Paare über die Hälften hinweg unverändert bleiben.

Füge beim Zusammenführen left[i] ≤ right[j] den Wert left[i] ein: Jeder noch wartende Wert rechts ist mindestens so groß wie right[j] und bildet daher keine Inversion. Andernfalls ist right[j] kleiner als left[i] und, da die linke Hälfte sortiert ist, kleiner als jeder noch wartende Wert links. Addiere deren Anzahl. Wenn zwei Werte gleich sind, wird der linke Wert zuerst eingefügt, sodass gleiche Werte nicht als Inversion zählen.

Bei [5, 3, 8, 1, 4] enthalten die Hälften 1 bzw. 2 Inversionen. Beim Zusammenführen von [3, 5] und [1, 4, 8] wird 1 an 3 und 5 vorbeigeschoben und 4 an 5 vorbei: 1 + 2 + 3 = 6.

Algorithmus

Kopiere nums und erstelle einen Puffer derselben Länge.
Gib beim Sortieren und Zählen eines Bereichs mit weniger als 2 Werten 0 zurück.
Teile ihn andernfalls bei mid und sortiere und zähle jede Hälfte.
Führe die Hälften mithilfe des Puffers zusammen: Nimm bei left[i] ≤ right[j] den linken Wert; andernfalls nimm den rechten Wert und addiere die Anzahl der noch nicht platzierten linken Werte.
Kopiere den zusammengeführten Bereich zurück und gib die Summe der drei Zählwerte zurück.

def sortAndCount(a, buf, lo, hi):
    # Sorts a[lo:hi] and returns the number of inversions inside it.
    if hi - lo < 2:
        return 0
    mid = (lo + hi) // 2
    count = sortAndCount(a, buf, lo, mid) + sortAndCount(a, buf, mid, hi)
    # Merge the two sorted halves, counting the pairs that cross the middle.
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        if a[i] <= a[j]:
            buf[k] = a[i]
            i += 1
        else:
            # a[j] is smaller than every left value not placed yet: a[i..mid-1].
            buf[k] = a[j]
            j += 1
            count += mid - i
        k += 1
    while i < mid:
        buf[k] = a[i]
        i += 1
        k += 1
    while j < hi:
        buf[k] = a[j]
        j += 1
        k += 1
    a[lo:hi] = buf[lo:hi]
    return count


def countInversions(nums):
    a = list(nums)  # sort a copy, not the caller's list
    return sortAndCount(a, [0] * len(a), 0, len(a))

Stolperfallen und Grenzfälle

1 hinzuzählen, wenn ein rechter Wert eingesetzt wird. Er passiert alle noch wartenden linken Werte, also addiere ihre Anzahl, mid - i.
Bei Gleichstand den rechten Wert nehmen und left[i] < right[j] als Test für die linke Seite verwenden. Dann zählt [2, 2, 2, 1] die gleichen 2er gegeneinander und gibt mehr als 3 zurück. Verwende ≤.
Beim Kopieren der übrigen Werte weiterzählen, nachdem eine Hälfte aufgebraucht ist. Für übrige linke Werte gibt es keinen rechten Wert mehr danach, und übrige rechte Werte wurden bereits mit jedem linken Wert verglichen.

Häufige Fragen3

Was ist eine Inversion in einem Array?

Eine Inversion ist ein Paar von Positionen i < j, bei dem nums[i] > nums[j] gilt, sodass ein größerer Wert vor einem kleineren steht. Eine sortierte Liste hat 0 Inversionen, und eine umgekehrte Liste mit unterschiedlichen Werten hat die größtmögliche Anzahl, n(n-1)/2. Die Anzahl entspricht der Zahl der benachbarten Vertauschungen, die Bubble Sort durchführt.

Wie hoch ist die Zeitkomplexität beim Zählen von Inversionen mit Merge Sort?

O(n log n) Laufzeit und O(n) zusätzlicher Speicherplatz für den Merge-Puffer. Jede der log n Mischebenen berührt jeden Wert einmal, also etwa 3 × 10^5 Schritte für 2 × 10^4 Werte. Die Schleife, die die Paare einzeln verarbeitet, hat eine Laufzeit von O(n²).

Können Inversionen ohne Merge-Sort gezählt werden?

Ja. Ein Fenwick-Baum (binär indizierter Baum) über den Rängen der Werte durchläuft die Liste einmal und ermittelt für jeden Wert, wie viele frühere Werte größer sind, in O(log n) pro Wert. Insgesamt ergibt das ebenfalls O(n log n). Ein balancierter Suchbaum, der die Größen der Teilbäume erfasst, funktioniert genauso.

def countInversions(nums):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

nums = [5, 3, 8, 1, 4]

Erwartete Ausgabe