İçeriğe geç

k sıralı diziyi birleştir

Kolay#k-way-merge#min-heap~20 dk

Görev tanımı

Problem

Sana her biri artan sırada sıralı k liste veriliyor ve bazıları boş olabilir. Onları tekrarlar dahil her değeri tutan tek bir artan listede birleştir. Her listeyi yalnız önünden oku ve herhangi bir anda liste başına birden fazla bekleyen değer tutma.

Örnekler

Input:  lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Input:  lists = [[], [0], []]
Output: [0]
Neden: boş listeler basitçe hiçbir katkı yapmaz
Input:  lists = []
Output: []
Neden: edge case: hiç liste yok

İpuçları

0 / 3

Hedef zaman
O(n log k)
Hedef alan
O(n)

Kısıtlar

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

Kodda değil de fikirde mi takıldın? K-way merge bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case