Come eliminare una lista collegata a $ \ mathcal {} O (n \ log n) $ tempo?

Question

Mi chiedevo come rimuovere i valori duplicati di una lista collegata a $ \ mathcal {} O (n \ lg n) $ tempo. Ho un'idea che, utilizzando merge sort quando vogliamo confrontare gli elementi per la scelta del piccolo, se sono uguali anticipo sul puntatore e basta considerare un elemento. Eventuali alternative?

Answer 1

1. Ordina la lista collegata a $ O (n \ log n) $ tempo.
2. passare attraverso ogni elemento della lista nel loro ordine e rimuovere l'elemento, se è lo stesso del precedente in $ O (n) $ tempo.

La complessità totale è di $ O (n \ log n) $, che è quello che stai cercando.

Answer 2

Si può fare in $ O (n) $ come segue.

1) Costruire una tabella hash attraversando la lista collegata e l'aggiunta di elementi alla tabella hash. In ogni iterazione, la ricerca nella tabella hash per l'essere considerata elemento corrente nell'iterazione. Se l'elemento non viene trovato, aggiungere alla tabella hash il valore dell'elemento come chiave, e 1 come valore corrispondente. Se invece si trova il corpo (che è stata inserita in un'iterazione precedente), è sufficiente aggiungere 1 al valore corrispondente e aggiorna la voce della tabella hash (aggiornati correttamente l'elemento molteplicità). Alla fine, la tabella hash conterrà al massimo $ n $ voci (ciò corrisponde al caso in cui l'elemento della lista collegata sono distinti), o meno di $ n $ elementi, con almeno una delle diciture che mostra una molteplicità maggiore di uno. Questo richiede $ O (n) $ tempo dal momento che in ciascuno dei $ n $ iterazioni il lavoro svolto sulla tabella di hash è di $ O (1) $.

2) Ora, attraversare la tabella hash e costruire una nuova lista collegata con l'aggiunta di un nodo per ogni elemento trovato. questo richiede al massimo $ O (n) $ dal momento che la tabella hash contiene al massimo $ n $ elementi, il lavoro fatto su ogni elemento della tabella hash è di $ O (1) $ e l'aggiunta di un nodo per la nuova lista prende $ O (1) $.

Quindi, la complessità totale è al massimo $ O (n) $.