Wie können verschiedene Werte in einer Liste in linearer Zeit gezählt werden?

Question

Ich kann daran denken, sie zu sortieren und dann jedes einzelne Element nacheinander durchzugehen, aber das ist nlogn. Gibt es eine lineare Methode, um bestimmte Elemente in einer Liste zu zählen?

Answer 1

Update: - deutliche und eindeutige

---

Wenn Sie suchen "einzigartig" Werte (wie in, wenn Sie ein Element sehen "JASON" mehr als einmal, als es nicht ist mehr eindeutig und sollte nicht gezählt werden)

Sie, dass durch die Verwendung eines HashMap in linearer Zeit tun;)

(Die verallgemeinerte/sprachunabhängig Idee ist Hash table)

Jeder Eintrag eines HashMap/Hash-Tabelle ist <KEY, VALUE> Paar wo die Schlüssel eindeutig sind (jedoch keine Einschränkungen für deren entsprechenden Wert in dem Paar)

Schritt 1:

iterieren all einmal Elemente in der Liste: O (n)

• Für jedes Element in der Liste zu sehen ist, zu überprüfen, um zu sehen, ob es in der HashMap ist bereits O (1), abgeschrieben
  • Wenn nicht, fügen Sie es dem HashMap mit dem Wert des Elements in der Liste als Schlüssel, und die Anzahl der Sie diesen Wert gesehen haben, soweit die VALUE O (1)
  • Wenn ja, haben die Anzahl der Male erhöhen Sie diese Taste so weit O (1)

Schritt 2 gesehen:

Iterieren durch die HashMap und zählen die Schlüssel mit Wert gleich genau 1 (also unique) O (n)

Analyse:

• Laufzeit: O (n), amortisiert
• Raum: O (U), wobei U die Anzahl der verschiedenen Werte ist.

---

Wenn suchen Sie „distinct“ Werte jedoch (wie in, wenn Sie wollen, zählen, wie viele verschiedenen Elemente sind), verwenden Sie einen HashSet anstelle einer HashMap/Hash Tabelle und dann einfach die Größe des HashSet abfragen.

Answer 2

Sie können this extremely cool O(n)-time and O(1)-space in-place algorithm zum Entfernen von Duplikaten anpassen, um bestimmte Werte zu zählen - zählen Sie einfach die Anzahl der Werte, die dem Sentinel-Wert entsprechen, in einem abschließenden O (n) -Pass und subtrahieren Sie diesen von der Größe der Liste.

Answer 3

Fügen Sie jedes Element der Liste zu einem HashSet hinzu und überprüfen Sie dann die size (Kardinalität) des HashSet, die die Anzahl der verschiedenen Werte in der Liste ist.