Overview
Häufigkeitsanalyse von Elementen mit einem Dictionary (Hash Map) in O(1) durchschnittlich pro Zugriff.
Analogy
Wörter in einem Text zählen: ein Notizbuch mit Wort als Schlüssel und Anzahl als Wert.
Step-by-step
- Erstelle leeres Dict count = {}.
- Für jedes Element e: count[e] = count.get(e, 0) + 1.
- Oder: verwende collections.Counter(iterable) direkt.
- Abfrage: count[e] liefert O(1) im Durchschnitt.
Visual
['a','b','a','c','b','a'] → {'a':3, 'b':2, 'c':1}
Common mistakes
- KeyError wenn Schlüssel nicht vorhanden – dict.get(key, 0) oder defaultdict(int) verwenden.
- Counter ist kein reguläres Dict – fehlende Schlüssel geben 0 zurück, nicht KeyError.
Practice questions
- Häufigste k Elemente mit Counter.most_common(k) finden.
- Zwei Strings auf Anagramm-Eigenschaft prüfen mit Counter-Vergleich.
Time
O(n) Aufbau, O(1) Ø Zugriff
Space
O(k) wobei k = Anzahl unterschiedlicher Elemente