Una estructura de datos para n elementos y operaciones O(1)

Proponga una estructura de datos para lo siguiente: 

La estructura de datos contendría elementos de 0 a n-1. No hay orden en los elementos (sin requisito de orden ascendente/descendente) 

La complejidad de las operaciones debe ser la siguiente: 

• Inserción de un elemento – O(1) 
• Eliminación de un elemento – O(1) 
• Encontrar un elemento – O(1) 

Recomendamos encarecidamente minimizar el navegador y probarlo usted mismo primero. 

Una array booleana funciona aquí. Array tendrá valor ‘verdadero’ en i-ésimo índice si i está presente, y ‘falso’ si está ausente. 

Inicialización: 

Creamos una array de tamaño n e inicializamos todos los elementos como ausentes. 

void initialize(int n)
{
  bool A[n];
  for (int i = 0; i<n; i++)
    A[i] = {0}; // or A[n] = {false};
}

Inserción de un elemento: 

void insert(unsigned i)
{
   /* set the value at index i to true */
   A[i] = 1; // Or A[i] = true;
}

Eliminación de un elemento: 

void delete(unsigned i)
{
  /* make the value at index i to 0 */
  A[i] = 0;  // Or A[i] = false;
}

Encontrar un elemento: 

// Returns true if 'i' is present, else false
bool find(unsigned i)
{
    return A[i];
}

Como ejercicio, cambie la estructura de datos para que contenga valores de 1 a n en lugar de 0 a n-1.