Por “selección de un elemento aleatorio”, ¿quiere decir “verificar si un valor dado está presente en la estructura de datos” o “devolver uno de los valores de la estructura de datos al azar?” Porque esos son requisitos muy diferentes.
Suponiendo que realmente quiere decir lo primero, una tabla hash / mapa hash lo suficientemente grande con una buena función hash proporcionará (¡amortizado!) Inserción, eliminación y recuperación en tiempo constante. Si espera muchos duplicados y necesita la estructura de datos para rastrearlos, una opción sería colocar un recuento de referencia en cada entrada: establezca el recuento en 1 en la inserción inicial, incremente el recuento de una entrada si inserta el mismo valor nuevamente, disminuirlo cuando “elimine”, y solo eliminarlo realmente cuando el recuento llegue a cero. (Si no le importa volver a contar los duplicados, puede verificar primero si el valor está presente y omitir la inserción si lo está).
Si necesita un tiempo constante garantizado , necesita algo con un mapeo 1 a 1 (biyectivo) a todos sus valores posibles. Lo más simple que se me ocurre sería un mapa de bits o una matriz de punteros, con un espacio por valor posible. Para una gran cantidad de valores (como 2 ** 32), en la práctica probablemente desee una matriz dispersa con algún tipo de estructura de árbol para que pueda averiguar rápidamente si una sección completa de la matriz está vacía o no. Esto requiere una sobrecarga de O (log (número máximo de valores)) por operación, pero es una sobrecarga constante sin importar cuántos valores se hayan insertado realmente, por lo que en ese sentido sigue siendo O (1). Puede realizar un recuento como se describió anteriormente para tratar con los duplicados de seguimiento.
- Cómo contar el número de enteros palindrómicos dentro de un rango [A, B] donde A y B pueden ser de hasta 10 ^ 17
- ¿Es posible codificar un programa que, dada una secuencia finita, encuentra al menos 2 reglas posibles que generan las series restantes?
- ¿Es correcto mi nuevo estado de ánimo? Ingresé a la programación desde un punto de vista de programación algorítmica y, como tal, tengo una inclinación a querer saber cómo funcionan las cosas debajo. Pero ahora, después de un tiempo en el mundo de los desarrolladores, finalmente tengo que darme cuenta de que se trata menos de eso. ¿Lo que usted dice?
- ¿Utiliza el cerebro un proceso de recursión?
- ¿Dónde puedo encontrar problemas difíciles de algoritmo / estructura de datos?
