Pular para o conteúdo

Mesclar K sequências ordenadas

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

A missão

Problema

Você recebe k listas, cada uma ordenada em ordem crescente, e algumas delas podem estar vazias. Combine-as em uma única lista crescente com todos os valores, duplicados incluídos. Leia cada lista só pela frente e não guarde mais de um valor em espera por lista em nenhum momento.

Exemplos

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ê: listas vazias simplesmente não contribuem com nada
Input:  lists = []
Output: []
Por quê: edge case: nenhuma lista

Dicas

0 / 3

Tempo-alvo
O(n log k)
Espaço-alvo
O(n)

Restrições

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

Travou na ideia, e não no código? K-way merge explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado