k sıralı diziyi birleştir
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
Her şeyi tek bir listeye döküp sıralamak, her listenin zaten sıralı olduğu gerçeğini yok sayar.
Herhangi bir anda çıktının sonraki değeri listelerden birinin ön değeri olmalı. Yalnız bu k ön değerin en küçüğüne ihtiyacın var.
Boş olmayan her listenin ön değerini, listesi ve konumuyla etiketlenmiş halde bir min-heap'e koy. En küçüğü pop et, çıktıya ekle ve varsa aynı listeden sonraki değeri push et. Heap boşalınca dur.
- 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
Çözüm
Sonraki çıktı değeri her zaman mevcut ön değerlerin en küçüğüdür; bu yüzden liste başına tam olarak bir ön değer tutan bir min-heap onu O(log k)'da verir. Her eleman liste indeksini ve konumunu taşır; böylece bir pop'tan sonra heap az önce değer veren listeden yeniden doldurulur, bu da liste başına bir kuralını korur. Liste indeksiyle etiketlemek eşit değerler arasındaki eşitlikleri de başka hiçbir şeyi karşılaştırmadan bozar. Toplam n değerle zaman O(n log k), heap en fazla k eleman tutar.
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([])) # -> []Kodda değil de fikirde mi takıldın? K-way merge bunu anlatıyor.