Es esencialmente una lista de listas. Una solución simple de tiempo O (N) que involucra espacio adicional sería atravesar todos los nodos en todas las listas, uno por uno, e incrementar los recuentos en una tabla hash externa, y luego elegir el elemento con el kth menos recuento de los valores en la tabla hash .
Esto supone que no hay ciclos durante el desplazamiento, y que las listas asociadas con cada nodo son distintas (no se cruzan). En caso de que se deban manejar los ciclos, se puede realizar un seguimiento de los nodos visitados (nuevamente en otra tabla hash), detener el recorrido de la lista actual en caso de volver a visitar el nodo y pasar a la siguiente lista.
No parece que pueda hacerlo de manera más óptima a tiempo, dado que no se puede afirmar la enésima singularidad ‘saltando algunos nodos’, es decir, todos los nodos tienen que ser visitados. Tal vez, uno puede intentar llegar a soluciones más inteligentes que no involucren el espacio adicional O (N) que requiere esta solución.
- Cómo agregar números de dos listas vinculadas
- ¿Por qué se han desarrollado los algoritmos de ordenamiento O (n ^ 2) (como el ordenamiento por inserción y el ordenamiento por burbuja) y para qué se utilizan?
- ¿Cuáles son algunos buenos libros para aprender y practicar estructuras de datos y algoritmos?
- ¿Cuál es la diferencia entre los cursos avanzados de algoritmos 6.046 y 6.854 en el MIT?
- ¿Cuál es el mejor algoritmo para la optimización convexa sin restricciones de propósito general?
