Comment purger une liste chaînée en $ \ mathcal {O} (n \ log n) $ temps?

Question

Je me demandais comment supprimer des doublons dans une liste liée à $ \ mathcal {O} (n \ n lg) $ temps. J'ai une idée en utilisant sorte de fusion lorsque l'on veut comparer les éléments pour choisir le petit, si elles sont égales avance sur le pointeur et il suffit de considérer un élément. Toute solution de rechange?

Answer 1

1. Trier la liste chaînée dans O $ (n \ log n) $ temps.
2. Allez à travers chaque élément de la liste dans l'ordre et de supprimer l'élément, si elle est la même que la précédente O $ (n) $ temps.

La complexité totale est O $ (n \ log n) $, ce qui est ce que vous recherchez.

Answer 2

Vous pouvez le faire en O $ (n) $ comme suit.

1) construire une table de hachage en parcourant la liste liée et en ajoutant les éléments de la table de hachage. Dans chaque itération, recherche la table de hachage pour l'être l'élément courant considéré dans l'itération. Si l'élément ne se trouve pas, ajouter à la table de hachage de la valeur de l'élément comme la clé, et 1 comme la valeur correspondante. Si vous trouvez l'élément au lieu (qui a été inséré dans une itération précédente), il vous suffit d'ajouter 1 à la valeur correspondante et mettre à jour l'entrée de table de hachage (mise à jour correctement la multiplicité des éléments). A la fin, votre table de hachage contiendra au maximum $ n $ entrées (ce qui correspond au cas où l'élément dans la liste chaînée sont distincts), ou moins que les éléments $ n $, avec au moins l'une des entrées montrant une multiplicité supérieur à un. Cela prend O $ (n) $ depuis le temps dans chacune des itérations $ n $ le travail effectué sur la table de hachage est O $ (1) $.

2) Maintenant, traverse la table de hachage et de construire une nouvelle liste chaînée par l'ajout d'un noeud pour chaque élément trouvé. cela prend au plus O $ (n) $ depuis la table de hachage contient au plus $ n éléments $, le travail effectué sur chaque élément de la table de hachage est O $ (1) $ et l'ajout d'un noeud à la nouvelle liste prend $ O (1) $.

Par conséquent, la complexité totale est au plus O $ (n) $.