comment supprimer des doublons d'un tableau sans tri

Question

J'ai un tableau qui peut contenir des objets en double. Je me demande s'il est possible de trouver et supprimer les doublons dans le tableau: - sans tri (strict requis) - sans utiliser un tableau secondaire temporaire - possibily en O (N), avec N le nb des éléments dans le tableau

Dans mon cas, le tableau est un tableau Lua, qui contient des tableaux:

t={ 
{a,1}, 
{a,2}, 
{b,1}, 
{b,3}, 
{a,2} 
} 

Dans mon cas, t [5] est un double de t [2], alors que t [1] ne .

Answer 1

Pour résumer, vous avez les options suivantes:

• temps: O (n^2), pas de mémoire supplémentaire - pour chaque élément du tableau en recherche une égale linéairement
• heure: O (n * log n), pas de mémoire supplémentaire - trier d'abord, parcourir linéairement le tableau après
• temps: O (n), mémoire: O (n) - utiliser une table de recherche (edit: ce n'est probablement pas une option en tant que table s ne peut pas être des clés dans d'autres tables autant que je me souvienne)

Choisissez un. Il n'y a aucun moyen de faire ce que vous voulez en O (n) temps sans mémoire supplémentaire.

Answer 2

Itérer le tableau, coller toutes les valeurs dans un hachage, en vérifiant s'il existe en premier. Si cela supprime du tableau original (ou n'écrit pas dans le nouveau). Pas très efficace en mémoire, mais seulement 0 (n) puisque vous ne faites qu'itérer le tableau une fois.

Answer 3

Ne peut pas être fait en O (n), mais ...

ce que vous pouvez faire est

• Itérer à travers le tableau
• Pour chaque recherche de membre avant pour les répétitions, retirez les .

complexité dans le pire des cas est O (n^2)

Answer 4

Oui, selon la façon dont vous le regardez.

Vous pouvez remplacer l'insertion d'objet pour empêcher l'insertion d'éléments en double. C'est O (n) par insertion d'objet et peut se sentir plus rapide pour les tableaux plus petits.

Si vous fournissez l'insertion et la suppression d'objets triés, alors c'est O (log n). Essentiellement, vous gardez toujours la liste triée comme vous insérez et supprimez de sorte que la recherche d'éléments est une recherche binaire. Le coût ici est que l'extraction de l'élément est maintenant O (log n) au lieu de O (1).

Cela peut également être mis en œuvre efficacement en utilisant des choses comme des arborescences red-black et multitree, mais au prix de la mémoire supplémentaire. De telles implémentations offrent plusieurs avantages pour certains problèmes. Par exemple, on peut avoir un comportement de type O (log n) même très très grand avec une petite empreinte mémoire en utilisant des arborescences imbriquées. L'arborescence de niveau supérieur fournit une sorte de vue d'ensemble de l'ensemble de données, tandis que les sous-arborescences fournissent un accès plus précis en cas de besoin. Par exemple, pour voir cela, supposons que nous ayons N éléments. Par exemple, pour voir ceci, supposons que nous avons N éléments. Nous pourrions diviser cela en n1 groupes.Chacun de ces groupes pourrait ensuite être divisé en n2 autres groupes et ces groupes en n2 groupes. D'où nous avons une profondeur de N/n1n2 ...

Comme vous pouvez le voir, le produit de n peut devenir très énorme très rapidement même pour les petits n. Si N = 1 billion d'éléments et n1 = 1000, n2 = 1000, n3 = 1000 il faut seulement 1000 + 1000 + 1000 + 1000 s = 4000 par temps d'accès. De plus, nous n'avons que 10^9 fois l'empreinte mémoire de chaque nœud. Comparez cela à la moyenne de 500 milliards de temps d'accès requis pour une recherche linéaire directe. Il est plus de 100 millions de fois plus rapide et 1000 fois moins de mémoire qu'un arbre binaire mais environ 100 fois plus lent! (bien sûr, il y a des frais généraux pour garder l'arbre cohérent, mais même cela peut être réduit).

Si nous devions utiliser un arbre binaire alors il aurait une profondeur d'environ 40. Le problème est qu'il y a environ 1 trillion de nœuds, ce qui représente une énorme quantité de mémoire supplémentaire. En stockant plusieurs valeurs par nœud (et dans le cas ci-dessus, chaque nœud est en fait des valeurs partielles et d'autres arborescences), nous pouvons réduire considérablement l'empreinte mémoire tout en conservant des performances impressionnantes.

L'accès essentiellement linéaire prévaut à des nombres inférieurs et les arbres prévalent à des nombres élevés. Des arbres. Les arbres consomment plus de mémoire. En utilisant multitree, nous pouvons combiner le meilleur des deux mondes en utilisant un accès linéaire sur des nombres plus petits et en ayant un plus grand nombre d'éléments par nœud (par rapport aux arborescences binaires).

tel de l'arbre ne sont pas anodins pour créer mais essentiellement suivre la même nature algorithmique de l'arbre binaire standard, rouge-noir de l'arbre, de l'arbre AVL, etc ...

Donc, si vous faites affaire avec de grands ensembles de données, il n'est pas un énorme problème pour la performance et la mémoire. Essentiellement, comme vous le savez probablement, quand l'un monte, l'autre diminue. Multitree, sorte de trouver le support optimal. (En supposant que vous avez choisi correctement vos tailles de noeuds)

---

La profondeur de la multitree est N/produit (n_k, k = 1..m). L'empreinte mémoire est le nombre de nœuds qui est produit (n_k, k = 1..m) (qui peut généralement être réduit d'un ordre de grandeur ou éventuellement n_m)