Come contare i valori distinti in una lista in tempo lineare?

Question

Posso pensare di ordinarli e poi andare su ogni elemento uno per uno, ma questo è nlogn. Esiste un metodo lineare per contare elementi distinti in una lista?

Answer 1

Aggiornamento: - distinta vs. unica

---

Se siete alla ricerca di "unici" valori (come se si vede un elemento di "Jason" più di una volta, che non è più unico e non devono essere conteggiati)

che si può fare in un tempo lineare utilizzando un HashMap;)

(La generalizzata/lingua-agnostic idea è Hash table)

Ciascuna voce di un HashMap tavolo/Hash è <KEY, VALUE> coppia in cui le chiavi sono unici (ma restrizioni al loro corrispondente valore della coppia)

Fase 1:

scorrere tutti elementi nell'elenco volta: O (n)

• per ogni elemento nell'elenco visto, verificare se è nella HashMap già O (1), ammortizzata
  • In caso contrario, aggiungerlo alla HashMap con il valore dell'elemento della lista come chiave, e il numero di volte che hai visto questo valore per quanto riguarda la VALORE O (1)
  • Se è così, incrementare il numero di volte che hai visto questa chiave finora O (1)

Step2:

Scorrere HashMap e contare le chiavi con valore pari esattamente 1 (quindi unici) O (n)

Analysis:

• Durata: O (n), ammortizzato
• Spazio: O (U), dove U è il numero di valori distinti.

---

Se, invece, siete alla ricerca di "distinti" valori (Come se si vuole contare quanti diversi elementi ci sono), utilizzare un HashSet invece di una HashMap/Hash tabella, quindi interrogare semplicemente la dimensione di HashSet.

Answer 2

È possibile adattare this extremely cool O(n)-time and O(1)-space in-place algorithm per la rimozione di duplicati all'attività di conteggio di valori distinti: è sufficiente contare il numero di valori uguale al valore sentinella in un passaggio O (n) finale e sottrarlo dalla dimensione dell'elenco.

Answer 3

Aggiungere ogni elemento dell'elenco a HashSet e quindi controllare lo size (cardinalità) di HashSet, che è il numero di valori distinti nell'elenco.