Algoritmos de Java: fusionar k listas ordenadas (LeetCode) by@rakhmedovrs
112,196 lecturas

Algoritmos de Java: fusionar k listas ordenadas (LeetCode)

2022/06/27
por @rakhmedovrs 112,196 lecturas
tldt arrow
ES
Read on Terminal Reader

Demasiado Largo; Para Leer

pedir descripción: Se le proporciona una matriz de k listas de listas vinculadas, cada lista vinculada se ordena en orden ascendente. Combine todas las listas vinculadas en una lista vinculada ordenada y devuélvala. Ejemplo 1: Entrada: listas = [[1,4,5],[1,3,4],[2,6]] Salida: [1,1,2,3,4,4,5,6] Explicación: Las listas enlazadas son: [ 1->4->5, 1->3->4, 2->6 ] combinándolos en una lista ordenada: 1->1->2->3->4->4->5->6
featured image - Algoritmos de Java: fusionar k listas ordenadas (LeetCode)
Ruslan Rakhmedov HackerNoon profile picture

@rakhmedovrs

Ruslan Rakhmedov

Senior Software Engineer. As a hobby I do competitive programming...

Aprender Mas
LEARN MORE ABOUT @RAKHMEDOVRS'S EXPERTISE AND PLACE ON THE INTERNET.
react to story with heart

Descripción de la tarea:

Se le proporciona una matriz de k listas de lists vinculadas, cada lista vinculada se ordena en orden ascendente.

Combine todas las listas vinculadas en una lista vinculada ordenada y devuélvala.

Ejemplo 1:

 Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6

Solución:

Antes de saltar a la solución de este problema, recordemos qué es la lista enlazada.

image

Una lista enlazada es una estructura de datos que consiste en nodos conectados entre sí por uno (lista enlazada única) de dos punteros (lista enlazada doble). Cada nodo generalmente contiene algún valor y apunta al siguiente nodo. El primer nodo se llama Head y el último nodo se llama Tail. La cola como puntero siguiente generalmente tiene un valor nulo.

En esta tarea, estamos tratando con listas enlazadas ordenadas. Lo que significa que todos los valores en cada nodo están ordenados. Cada nodo en cada lista tiene un valor menor o igual que el valor en un nodo al que apunta. Para visualizarlo aquí hay un ejemplo de lista enlazada ordenada.

image

Teniendo una comprensión de lo que es la lista enlazada ordenada, podríamos resolver la versión más fácil de nuestro problema. ¿Cómo fusionarías 2 listas enlazadas ordenadas?

image

Y la respuesta es - extremadamente simple. Compara los encabezados de cada lista. Elija el nodo con el valor mínimo. Adjúntelo a su respuesta y ajuste el puntero al siguiente nodo en la lista de la que seleccionó un nodo. Hazlo hasta que una de las cabezas no sea igual a nula. Una vez que llegue a ese punto, simplemente puede adjuntar el resto a su respuesta.

image

Ahora estamos cerca de resolver el problema real. De la tarea más fácil, vemos que la clave de la solución es tomar el nodo con el valor más pequeño y adjuntarlo a la respuesta ajustando el puntero.

Teniendo una matriz de K encabezados de lista ordenados, podríamos iterarlo y cada vez elegir un nodo con el valor más pequeño. Resolvería el problema pero la complejidad del tiempo es terrible.

La mejor manera será tomar el encabezado de cada lista y agregarlo a una cola de prioridad. Priority Queue es otra estructura de datos que proporciona obtener el valor más pequeño o más grande en tiempo constante O(1). Y agregando o eliminando este valor en el tiempo O (log n), que es lo suficientemente bueno para nuestra tarea. A menudo, la cola de prioridad se denomina montón binario según la forma de almacenar elementos. Podría describirlo en un próximo artículo.

 public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } ListNode dummy = new ListNode(0); ListNode prev = dummy; ListNode current; ListNode next; PriorityQueue<ListNode> minHeap = new PriorityQueue<>( Comparator.comparingInt(head -> head.val) ); for (ListNode node : lists) { if (node != null) { minHeap.add(node); } } while (!minHeap.isEmpty()) { current = minHeap.remove(); if (current == null) { continue; } next = current.next; current.next = null; prev.next = current; prev = current; if (next != null) { minHeap.add(next); } } return dummy.next; }

En la línea 8 creamos un nodo "ficticio", que será nuestro encabezado temporal. Nos ayudará a devolver fácilmente la cabeza real de las listas enlazadas ordenadas llamando a dummy.next

En las líneas 13 a 15 creamos una cola de prioridad. Necesitamos ordenar los elementos en él. Para este propósito proporcionamos Comparator.

En las líneas 17 a 23 agregamos todos los encabezados no nulos a la cola de prioridad.

En las líneas 25–42 tenemos el ciclo while principal que contiene la lógica principal.

Actualizamos el nodo actual eliminando el nodo con el valor mínimo de la parte superior de nuestra cola de prioridad. Luego actualizamos el siguiente puntero obteniendo el siguiente nodo del actual. También necesitamos actualizar el puntero anterior. Puede pensar en el puntero anterior como un puntero a la cola temporal de la lista enlazada que estamos construyendo. Y por último, pero no menos importante, si el siguiente enlace no es nulo, debemos devolverlo a la cola de prioridad.

image

Después de ejecutar los pasos anteriores en el ejemplo 1, obtendremos el estado representado a continuación. No lo aplané intencionalmente. Para mostrarle la transición del estado original al estado final

image

El algoritmo mencionado anteriormente nos da el siguiente resultado.

image
La complejidad de tiempo para nuestra solución es O(N log K) donde N - es el número total de nodos en todas las listas donde K - es el número de listas enlazadas ordenadas que tenemos.

La complejidad del espacio para nuestra solución es O(N) donde N - es el número total de nodos para crear una respuesta más O(K) donde K - es el número de listas enlazadas ordenadas que tenemos. De acuerdo con la notación O grande, podemos omitir O(K) porque podría ser igual o menor que O(N) en términos de varios elementos.

Espero que este artículo te haya ayudado a comprender la lógica que se esconde detrás de esta difícil tarea. ¡Gracias por leer! Esperamos sus comentarios. Hasta pronto ✌

Este artículo se publicó por primera vez aquí.

HISTORIAS RELACIONADAS

L O A D I N G
. . . comments & more!
Hackernoon hq - po box 2206, edwards, colorado 81632, usa