Algorithmen und Datenstrukturen · Junior · Frage 61 von 75
Wie zählt man in O(n), wie oft jedes Wort in einer Liste vorkommt?
- 1Verschachtelte Schleifen, die jedes Wort mit jedem vergleichen
- 2Eine
Mapvon Wort zu Zähler nutzen und in einem Durchlauf erhöhen - 3Die Wörter sortieren und für jedes
indexOfaufrufen
Antwort zeigen
Richtige Antwort: Eine Map von Wort zu Zähler nutzen und in einem Durchlauf erhöhen
Erklärung
Ein Durchlauf mit counts.set(w, (counts.get(w) ?? 0) + 1) ist im Schnitt O(n). Häufigkeiten mit einer Hash-Map zu zählen ist einer der häufigsten Bausteine in Interview-Aufgaben.