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?Come contare i valori distinti in una lista in tempo lineare?
risposta
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.
È 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.
- 1. Contare valori distinti utilizzando elasticsearch
- 2. Come contare i valori distinti in una colonna di un gruppo di panda per oggetto?
- 3. Contare il numero di valori distinti in un vettore
- 4. Seleziona tutti i valori distinti in una colonna utilizzando LINQ
- 5. Come invertire un grafico in tempo lineare?
- 6. Conta valori distinti
- 7. Ordinamento in tempo lineare?
- 8. Trova valori distinti, i conteggi non distinti in elasticsearch
- 9. LINQ Get valori distinti e riempire LISTA
- 10. Come contare più valori in una matrice
- 11. Come contare i valori NaN in una colonna in Pandas DataFrame
- 12. Come contare i valori univoci per categoria in Excel
- 13. Come contare elementi distinti su campi specifici in QueryDSL
- 14. In loop su valori distinti
- 15. Come ottenere valori distinti in SQL Query
- 16. LINQ: valori distinti
- 17. Come posso ottenere valori distinti in COALESCE()
- 18. Come contare i valori VERO in un vettore logico
- 19. SQL: numero di conteggi di valori distinti in ogni colonna
- 20. Query MongoDB per i valori distinti ordinate
- 21. Come contare i bambini in un albero
- 22. Come contare il numero di valori numerici in una colonna
- 23. migliorare una query lista amici: contare i comuni amici
- 24. Inserire valori distinti da una tabella in un'altra tabella
- 25. Bigquery selezionare valori distinti
- 26. Sfogliando i valori booleani in una lista Python
- 27. count valori distinti nel foglio di calcolo
- 28. Come ordinare una lista controllando i valori in una sottolista in python?
- 29. come ottenere valori distinti da json in jquery
- 30. Contare i frame in una griglia 2D
Ecco come trovare un numero di valori univoci nell'elenco e la domanda riguarda il rilevamento di un numero di valori distinti. Per contare valori distinti utilizzare [HashSet] (http://docs.oracle.com/javase/6/docs/api/java/util/HashSet.html). Basta aggiungere ogni elemento della lista all'HashSet e controllarne la cardinalità. – user1871166
Non vorreste contare TUTTI i valori in HashMap nel passo 2, piuttosto che quelli con valore 1? Facendolo in questo modo conterei solo gli elementi che appaiono esattamente una volta, ad es. l'elenco {PAT, PAT, STEVE, JOEL} risulterebbe in un valore di 2 (solo STEVE e JOEL si verificano una volta) anziché il valore corretto di 3 nomi distinti. – Jason
Nota! C'è una discrepanza di interpretazione qui: la mia ipotesi è che se vedi un particolare valore 2 o più volte, non è più "distinto"/"unico" - ma lo modificherò per essere più chiaro. –