Structure de données qui prend en charge les éléments suivants en temps O(1) : initialisation, insertion, suppression, recherche d'un élément, suppression de tous les éléments.

Question

Question d'entretien :

P toutes les opérations suivantes en temps O(1) : initialisation, insertion d'un élément, suppression d'un élément, recherche d'un élément, suppression de tous les éléments. d'un élément, recherche d'un élément, suppression de tous les éléments.

Une table de hachage (en supposant qu'il n'y ait pas de collisions, c'est-à-dire dans le meilleur des cas) permettrait l'insertion et la recherche en O(1). Je ne suis pas sûr de la suppression par contre...une idée ?

Answer 1

Question très intéressante !

En supposant que l'allocation de mémoire et la désallocation sont O(1), alors une O(1) est possible pour tous.

Pour cela, nous utilisons l'astuce de Hopcroft et Ullman qui nous permet d'utiliser des tableaux de taille n, sans avoir à passer Omega(n) temps à les initialiser.

Voir ici : http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/

Lors de l'insertion, nous utilisons simplement le tableau ci-dessus et le mettons à 1. Lors d'une recherche, si nous trouvons que l'élément du tableau n'est pas initialisé, nous retournons 0. Lors d'une suppression, nous lui attribuons la valeur 0.

Lors d'un delete all, nous libérons la structure de données et en utilisons une nouvelle.

Answer 2

OK je pense que si le N est dans la rage vous pouvez juste déclarer un tableau de N éléments

0)Initialize
memset(A,0,sizeof(A))

1) Insert i
A[i] = 1

2) Remove i
A[i] = 0

3) Find i 
if( A[i] )

4) Delete All
memset(A,0,sizeof(A))

Answer 3

La table de hachage peut être O(1) pour la suppression.

List<Object> hashTableData = new ArrayList<Object>();

Edit : le code est une implémentation possible des données stockées pour la table de hachage.

Answer 4

Je cherchais la solution à la même question !

Et j'ai trouvé un article où ils ont obtenu une complexité en temps constant pour les opérations d'insertion, de suppression et de recherche en utilisant le hachage et les cartes. Pendant l'insertion, en même temps que l'élément (clé), l'index est également stocké comme valeur de la clé.

Vous pouvez voir ici :

https://www.geeksforgeeks.org/design-a-data-structure-that-supports-insert-delete-search-and-getrandom-in-constant-time/

https://www.geeksforgeeks.org/design-a-data-structure-that-supports-insert-delete-getrandom-in-o1-with-duplicates/

Et un tableau booléen ferait les mêmes opérations en O(1).