Mesclar K sequências ordenadas
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
Despejar tudo em uma lista e ordenar ignora o fato de que cada lista já está em ordem.
A cada momento, o próximo valor da saída precisa ser o valor da frente de uma das listas. Você só precisa do menor desses k valores da frente.
Coloque o valor da frente de cada lista não vazia em um min-heap, marcado com a lista e a posição dele. Extraia o menor, adicione-o à saída e insira o próximo valor da mesma lista, se houver. Pare quando o heap esvaziar.
- 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
Solução
O próximo valor da saída é sempre o menor dos valores da frente atuais, então um min-heap com exatamente um valor da frente por lista o entrega em O(log k). Cada entrada carrega o índice da lista e a posição, então, depois de uma extração, o heap é reabastecido a partir da lista que acabou de ceder um valor, o que mantém a regra de um por lista. Marcar com o índice da lista também desempata valores iguais sem nunca comparar mais nada. Com n valores no total, o tempo é O(n log k) e o heap guarda no máximo k entradas.
import heapq
def merge_runs(lists):
heap = [(run[0], i, 0) for i, run in enumerate(lists) if run]
heapq.heapify(heap) # one front value per list
out = []
while heap:
value, i, j = heapq.heappop(heap)
out.append(value)
if j + 1 < len(lists[i]): # refill from the list just used
heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
return out
print(merge_runs([[1, 4, 5], [1, 3, 4], [2, 6]])) # -> [1, 1, 2, 3, 4, 4, 5, 6]
print(merge_runs([[], [0], []])) # -> [0]
print(merge_runs([])) # -> []Travou na ideia, e não no código? K-way merge explica isso.