Problem
An inversion is a pair of positions i < j with numbers[i] > numbers[j]. Count all inversions. Lists can be long, so a merge-sort based O(n log n) count is needed.
Implement count_inversions(numbers).
Input
numbers: The list of integers.
Output
Return the number of inversions.
Einschränkungen
0 ≤ length ≤ 200,000
Beispiele
Eingabe:
numbers = [2, 4, 1, 3, 5]
Erwartete Ausgabe:
expected = 3Eingabe:
std::vector<long long> numbers = {2, 4, 1, 3, 5};
Erwartete Ausgabe:
long long expected = 3;Eingabe:
long[] numbers = new long[] {2, 4, 1, 3, 5};
Erwartete Ausgabe:
long expected = 3;Erläuterung
Out-of-order pairs: (2,1), (4,1), (4,3): 3 inversions.
Eingabe:
numbers = [1, 2, 3]
Erwartete Ausgabe:
expected = 0Eingabe:
std::vector<long long> numbers = {1, 2, 3};
Erwartete Ausgabe:
long long expected = 0;Eingabe:
long[] numbers = new long[] {1, 2, 3};
Erwartete Ausgabe:
long expected = 0;Erläuterung
Already sorted: 0 inversions.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Eine Inversion wird gezählt, wenn eine Zahl auf der linken Seite während des Mergings größer bleibt als eine auf der rechten.
Hinweis 2
Teile die Liste rekursiv und zähle Kreuzpaare beim Zusammenführen sortierter Hälften.
Hinweis 3
Achte auf Duplikate: Gleiche Werte sind keine Inversionen, daher ist die Vergleichsrichtung wichtig.
Erwartete Komplexität
Zeit O(n log n), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.