Saltar al contenido

Fusionar k listas ordenadas

Fácil#k-way-merge#min-heap~20 min

La misión

Problema

Recibes k listas, cada una ordenada de forma ascendente, y algunas pueden estar vacías. Combínalas en una sola lista ascendente que contenga todos los valores, duplicados incluidos. Lee cada lista solo desde el frente y no guardes más de un valor en espera por lista en ningún momento.

Ejemplos

Input:  lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Input:  lists = [[], [0], []]
Output: [0]
Por qué: las listas vacías simplemente no aportan nada
Input:  lists = []
Output: []
Por qué: caso límite: no hay ninguna lista

Pistas

0 / 3

Tiempo objetivo
O(n log k)
Espacio objetivo
O(n)

Restricciones

  • each of the k lists is sorted ascending
  • some lists may be empty

¿Lo que te frena es la idea y no el código? K-way merge lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio