Inversionen mit einem BIT
Zählen Sie ungeordnete Paare effizient
Inversionen mit einem BIT ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was ist eine Inversion?
Eine Inversion ist ein Paar i < j mit a[i] > a[j]. Es handelt sich um ein einzelnes Paar in der falschen Reihenfolge. Die Anzahl solcher Paare misst, wie unsortiert ein Array ist.
Warum Inversionen wichtig sind
Die Anzahl der Inversionen entspricht der Anzahl der Vertauschungen, die ein Bubble-Sort durchführen würde. In Wettbewerbsaufgaben versteckt sich dieses Konzept oft in Fragen zu Rangfolgen und Unordnung.
Das naive Zählen ist zu langsam
Das Prüfen jedes Paars benötigt O(n^2). Für n ungefähr 100000 sind das zehn Milliarden Prüfungen – weit über dem Zeitlimit. Wir brauchen eine bessere Lösung. 🐢
Die BIT-Idee
Durchlaufen Sie das Array von links nach rechts und fragen Sie: Wie viele frühere Elemente sind größer als das aktuelle? Ein Fenwick-Baum beantwortet diese Frage während des Durchlaufs.
Nach Häufigkeiten zählen
Das BIT speichert eine Häufigkeitstabelle über den Werten. update(v, 1) hält fest, dass der Wert v in unserem bisherigen Durchlauf aufgetreten ist.
update(v, 1)Größer bedeutet Suffix
Frühere Werte, die größer als v sind, ergeben sich aus der Anzahl der bisher gesehenen Werte minus der Anzahl bis einschließlich v. Beim i-ten Element ist das i minus query(v).
inv += i - query(v)Koordinatenkompression
Wenn die Werte groß oder negativ sind, bilden Sie sie zunächst auf die Ränge 1..n ab. Diese Kompression hält das BIT klein, ohne die Reihenfolge zu verändern.
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}Der vollständige Durchlauf
Durchlaufen Sie das Array, addieren Sie die Anzahl der größeren Werte zur Summe und fügen Sie anschließend den aktuellen Wert ein. Die laufende Gesamtsumme ist Ihre Inversionsanzahl.
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)Laufzeit n log n
Jedes Element löst eine Abfrage und ein Update aus, beide in O(log n). Die gesamte Zählung ist daher in O(n log n) abgeschlossen. 🚀
Merge-Sort ist der Verwandte
Auch Merge-Sort zählt Inversionen in O(n log n), und zwar während seines Merge-Schritts. Die BIT-Variante ist unter Zeitdruck oft kürzer zu programmieren.
Achten Sie auf einen Überlauf
Die Anzahl der Inversionen kann ungefähr n zum Quadrat geteilt durch zwei erreichen, also sehr groß werden. Python-Ganzzahlen sind unbegrenzt, aber in anderen Sprachen benötigen Sie einen 64-Bit-Datentyp.
Kurztest
Testen Sie, ob Sie die Laufzeit des Durchlaufs verstanden haben.
Zusammenfassung: Unordnung zählen
Sie haben Inversionen in O(n log n) gezählt, indem Sie das Array von links nach rechts durchlaufen und ein BIT gefragt haben, wie viele größeren Werte zuvor aufgetreten sind. Komprimieren Sie die Werte bei Bedarf. ✅
Häufig gestellte Fragen
Ist die Lektion „Inversionen mit einem BIT“ kostenlos?
Ja — der vollständige Text von „Inversionen mit einem BIT“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Inversionen mit einem BIT“?
Zählen Sie ungeordnete Paare effizient Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Inversionen mit einem BIT“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Fenwick-Baum für Präfixsummen
- Inversionen mit einem BIT
- Segmentbaum: Aufbau und Abfragen
- Lazy Propagation für Bereichsaktualisierungen