Häufigkeiten zählen und gruppieren

Die Häufigkeitszählung gehört zu den vielseitigsten Mustern in Coding-Interviews. Indem Sie erfassen, wie oft jedes Element in einer Liste oder einem String vorkommt, können Sie Fragen zu Duplikaten, Anagrammen, häufigsten Elementen und gültigen Anordnungen in O(n)-Zeit beantworten – deutlich effizienter als die Alternative aus Sortieren und Durchlaufen mit O(n log n).

Counter und defaultdict(int) sind die Standardwerkzeuge von Python. Beide erstellen eine Zuordnung von Elementen zu ihrer Anzahl; Counter unterstützt zusätzlich arithmetische Operationen und most_common.

LeetCode 242 „Gültiges Anagramm“: Ermitteln Sie, ob zwei Strings Anagramme voneinander sind. Zwei Strings sind Anagramme, wenn sie dieselben Zeichenhäufigkeiten aufweisen. Vergleichen Sie ihre Counter-Objekte oder sortieren Sie beide Strings. Die Verwendung von Counter benötigt O(n), das Sortieren O(n log n). Der Counter-Ansatz ist optimal und bildet die Definition direkt ab.

LeetCode 49 „Anagramme gruppieren“: Gruppieren Sie alle Anagramme in einer gegebenen Liste von Strings. Die zentrale Erkenntnis: Anagramme haben dieselbe sortierte Zeichenfolge. Verwenden Sie ein defaultdict(list), dessen Schlüssel das sortierte Tupel des Strings ist (Tupel sind hashbar). Jede Gruppe wird unter demselben Schlüssel gesammelt. Zeitaufwand: O(n × L log L), wobei L die maximale Stringlänge ist.

LeetCode 347 „Die k häufigsten Elemente“: Geben Sie die k häufigsten Elemente zurück. Ein direkter Ansatz benötigt O(n log n): Zählen Sie die Häufigkeiten, sortieren Sie nach absteigender Häufigkeit und nehmen Sie die ersten k Elemente. Der optimale O(n)-Ansatz verwendet Bucket-Sortierung: Erstellen Sie Buckets, die nach der Häufigkeit (1 bis n) indiziert sind, legen Sie jedes Element in den Bucket seiner Häufigkeit und durchlaufen Sie anschließend die Buckets von der höchsten zur niedrigsten Häufigkeit, bis Sie k Elemente gesammelt haben.

LeetCode 451 „Zeichen nach Häufigkeit sortieren“: Ordnen Sie einen String so um, dass die Zeichen in absteigender Reihenfolge ihrer Häufigkeit vorkommen. Zählen Sie die Häufigkeiten, sortieren Sie die Zeichen nach absteigender Häufigkeit und hängen Sie sie aneinander. Die Verwendung von most_common ist der klarste Ansatz in Python. Zeitaufwand: O(n log n) für das Sortieren der eindeutigen Zeichen nach ihrer Häufigkeit.

LeetCode 621 „Aufgabenplaner“: Ermitteln Sie bei gegebenen Aufgaben und einer Abkühlzeit n die minimale Zeit, um alle Aufgaben abzuschließen. Die entscheidende Erkenntnis: Die häufigste Aufgabe bestimmt die Struktur. Ordnen Sie max_count Kopien der häufigsten Aufgabe mit (n) Lücken an. Die minimale Gesamtzeit = max((max_count - 1) * (n + 1) + num_tasks_with_max_count, total_tasks). Wenn genügend unterschiedliche Aufgaben vorhanden sind, um die Lücken zu füllen, beträgt die Leerlaufzeit 0.

LeetCode 169 „Mehrheitselement“: Ermitteln Sie das Element, das mehr als n/2-mal vorkommt. Boyer-Moore ist zwar die optimale Lösung mit O(1) zusätzlichem Speicherplatz, aber mit Counter.most_common(1) lässt sich das Problem direkt in O(n)-Zeit und mit O(n) Speicherplatz lösen. Wenn im Interview O(1) Speicherplatz gefordert wird, stellen Sie Boyer-Moore als weiterführende Lösung vor; wenn zusätzlicher Speicherplatz zulässig ist, ist Counter klarer.

LeetCode 387 „Erstes eindeutiges Zeichen in einem String“: Ermitteln Sie den Index des ersten Zeichens, das genau einmal vorkommt. Ansatz mit zwei Durchläufen: Im ersten Durchlauf erstellen Sie eine Häufigkeitszählung; im zweiten Durchlauf finden Sie das erste Zeichen mit der Anzahl 1. Zeitaufwand: O(n), Speicherplatz: O(1), da das Alphabet auf 26 Zeichen festgelegt ist.

LeetCode 560 „Teilarraysumme gleich K“: Zählen Sie die Teilarrays, deren Summe k ergibt. Die Brute-Force-Lösung benötigt O(n²). Der O(n)-Ansatz: Führen Sie eine laufende Präfixsumme und eine Häufigkeitsmap der bisher gesehenen Präfixsummen. Für jede Position i entspricht die Anzahl der bei i endenden Teilarrays mit Summe k der Anzahl früherer Präfixsummen, die gleich (current_prefix_sum - k) sind. Initialisieren Sie die Map mit {0: 1}, um Teilarrays zu berücksichtigen, die bei Index 0 beginnen.

Counter unterstützt arithmetische Operationen: + führt Zählwerte zusammen (addiert sie), - subtrahiert (begrenzt das Ergebnis auf 0), & nimmt das Minimum (Schnittmenge) und | nimmt das Maximum (Vereinigung). Diese Operationen vereinfachen Probleme wie „gemeinsame Zeichen in mehreren Strings finden“ oder „die minimale Anzahl von Zeichen entfernen, damit ein String ein Anagramm eines anderen wird“.

Greifen Sie zur Häufigkeitszählung, wenn ein Problem Folgendes umfasst: zu prüfen, ob zwei Strings bis auf ihre Reihenfolge gleich sind (Anagramm), die häufigsten oder seltensten Elemente zu ermitteln, sicherzustellen, dass eine Sammlung die richtigen „Bestandteile“ enthält, oder ein Teilarray-/Substring-Problem in ein Präfixsummen-mit-Map-Problem umzuwandeln. Der entscheidende Punkt ist, dass die Reihenfolge innerhalb einer Gruppe keine Rolle spielt – nur die Anzahlen zählen.

Verwenden Sie aus Gründen der Klarheit immer Counter; wechseln Sie nur dann zu einem einfachen dict oder Array, wenn Sie eine feinere Kontrolle benötigen oder bei einem begrenzten Alphabet strikt O(1) Speicherplatz einhalten müssen.

Testen Sie Ihr Verständnis der in dieser Lektion behandelten Konzepte aus Data Structures & Algorithms — Coding Interview Prep.

In dieser Lektion haben Sie gelernt: Counter ermöglicht eine Häufigkeitszählung in O(n) mit most_common, arithmetischen Operatoren und Zugriffen mit dem Standardwert null, die Gruppierung nach einer kanonischen Form (sortiertes Tupel) löst das Gruppieren von Anagrammen in O(nL log L) und eine Präfixsumme mit Häufigkeitsmap reduziert das Problem der Teilarraysumme k von O(n²) auf O(n). Als Nächstes lösen wir das Problem der längsten aufeinanderfolgenden Sequenz und beschäftigen uns mit dem Entwurf eines LRU-Caches.