Idea básica
Para cada posición inicial, calcule qué tan lejos podemos llegar sin repetir un valor.
Para una sola posición inicial, esto es fácil de hacer. Avance desde la posición inicial, verificando cada valor recién encontrado con una tabla hash que contenga todos los valores encontrados anteriormente. Detente cuando alcances tu punto de partida original o un nodo que sería un duplicado de algo que has visto antes, y registra cuántos nodos visitaste antes de detenerte.
- ¿Qué es un algoritmo para emparejar 18 personas en los 816 grupos posibles de 3 con 6 grupos a la vez?
- Cómo construir un secuenciador de ADN
- ¿Qué significa si un futuro programador apesta u odia los algoritmos de aprendizaje y las estructuras de datos?
- ¿En qué punto una gran notación O de velocidad de aumento más rápida ignora una notación O grande de velocidad de aumento más lenta?
- ¿Cuáles son algunas buenas ideas sobre proyectos en algoritmos y / o estructuras de datos?
Este procedimiento lleva tiempo O (N) si hay N nodos en la lista, suponiendo que las operaciones de la tabla hash se ejecuten en O (1), porque si un duplicado no lo detiene antes, se detendrá después de visitar N nodos (y hacer N búsquedas de tablas hash y N inserciones de tablas hash).
Obtenemos la respuesta final al ver qué nodo inicial visitamos la mayoría de los nodos antes de detenernos. Aquí hay un problema: no sabemos qué nodo inicial deberíamos usar, por lo que si los probamos todos, pasaremos tiempo O (N) para cada una de las N posibles posiciones iniciales, haciendo que el algoritmo general [matemático] O ( N ^ 2) [/ matemáticas].
Optimizando la solución
Una cosa que es muy notable es que si ya ejecutó el procedimiento comenzando en el primer nodo y visitó K nodos antes de obtener un duplicado, cuando lo ejecute comenzando desde el segundo nodo, visitará, como mínimo, los nodos 2 a K. En esos nodos, estás repitiendo exactamente el mismo trabajo. Tal vez después de llegar al nodo K-th, vaya a visitar algunos nodos adicionales, pero hasta que llegue al nodo K-th, simplemente está duplicando su trabajo de antes.
En base a esto, tenemos la idea de no volver a ejecutar el procedimiento desde cero para cada posible punto de partida. Si cuando comenzamos en el nodo 1 llegamos al nodo K (y el nodo K era un duplicado), entonces simularemos pasar de los nodos 2 a K en un solo paso simplemente eliminando el valor del nodo 1 de la tabla hash del nodo valores (en lugar de restablecer la tabla hash y volver a hacer el recorrido, como antes).
Una vez que la tabla hash corresponde a un recorrido transversal que comienza en el nodo 2, vemos si ahora podemos tomar el nodo K sin que sea un duplicado (esto sucederá si el nodo 1 y el nodo K tienen el mismo valor), y si es así, intentamos expandir la ventana tanto como podamos con nodos más allá de eso. (Si el nodo K sigue siendo un duplicado, nos detenemos en el nodo K una vez más.) De cualquier manera, registramos la longitud de secuencia libre de duplicados comenzando en el nodo 2, e intentamos el siguiente punto de partida (con una reutilización similar de la tabla hash )
Análisis de la solución optimizada
Notamos que hay N posibles puntos de partida, y la “ventana libre de duplicados” de cada punto de partida no se extiende más de N elementos. Eso significa que el final de la ventana atravesará no más de 2N elementos en total a lo largo del algoritmo. En total, eliminamos como máximo N valores de la tabla hash, insertamos como máximo 2N valores y buscamos como máximo 2N valores. El otro trabajo realizado en los bucles es O (N). Por lo tanto, la complejidad del tiempo es O (N) . Nunca tenemos más de N valores en la tabla hash en un momento dado, por lo que la complejidad del espacio también es O (N) .
