Merge k Sorted Lists

Q: Quelle est la complexité temporelle de la fusion de k listes triées ?

Avec un tas min, la complexité est de O(N log k) , où N est le nombre total de valeurs et k le nombre de listes. Chaque valeur est insérée puis extraite une fois, et le tas contient au plus k entrées. La mémoire supplémentaire est de O(k) , en plus de la sortie.

Q: Pourquoi ne pas rassembler toutes les valeurs et les trier ?

C’est exact et cela prend un temps de O(N log N) . Cette méthode ne tient pas compte du fait que les listes sont déjà triées : elle paie donc log N pour chaque valeur, alors que le tas ne paie que log k , et elle nécessite de garder toutes les valeurs en mémoire en même temps. Le tas peut également fusionner des listes qui arrivent sous forme de flux.

DifficileTas Liste chaînée

+10

Vous recevez k listes d’entiers correspondant aux lignes de lists. Chaque ligne est triée par ordre non décroissant, les lignes peuvent avoir des longueurs différentes et aucune ligne n’est vide.

Fusionnez-les en une seule liste contenant chaque valeur de toutes les lignes, triée par ordre non décroissant, puis retournez-la. Une valeur présente plusieurs fois, dans une ou plusieurs lignes, apparaît autant de fois dans le résultat.

Fonction

mergeKLists(lists: integer-2d-array) → integer-array

listsinteger-2d-array: les listes triées, une par ligne, de longueurs éventuellement différentes
Renvoieinteger-array: chaque valeur de chaque ligne, dans une seule liste triée

Contraintes

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length, et toutes les lignes réunies contiennent au maximum 10⁴ valeurs
-10⁴ ≤ lists[i][j] ≤ 10⁴
Chaque ligne est triée par ordre non décroissant.

Exemples

Entrée: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
Sortie: [1, 2, 3, 4, 5, 6, 9, 10]
Explication: Les lignes commencent par 2, 1 et 3, donc 1 vient en premier. Les premiers éléments sont ensuite 2, 4 et 3, donc 2 suit, et ainsi de suite. La troisième ligne s'arrête après 5, laissant 6, 9 et 10.

Entrée: lists = [[5], [-2, 5, 7], [0, 5]]
Sortie: [-2, 0, 5, 5, 5, 7]
Explication: Les trois 5 proviennent de trois lignes différentes et les trois restent. Le nombre négatif -2 se classe avant 0.

Pour aller plus loin

Trouvez l’intervalle le plus petit [a, b] contenant une valeur de chaque ligne. Un tas des têtes de ligne, associé à la plus grande tête, permet-il d’y parvenir en O(N log k) ?

Solution

Chaque ligne est triée, donc la plus petite valeur inutilisée est toujours la première valeur inutilisée d’une ligne, sa tête. Parcourir les k têtes coûte k étapes pour chacune des N valeurs. Un tas min des têtes fournit la plus petite en O(log k), ce qui réduit le coût total de O(N·k) à O(N log k).

Comparer les k têtes pour chaque valeur

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Gardez un index pos[r] en tête de chaque ligne. À chaque tour, lisez toutes les têtes, ajoutez la plus petite et avancez l’index de cette ligne : c’est l’étape de fusion du tri par fusion, étendue de deux listes à k. Dans le premier exemple, les têtes commencent par 2, 1 et 3 ; 1 est donc ajouté et la tête de la deuxième ligne devient 4.

Chacune des N valeurs nécessite un parcours de toutes les k lignes. Avec 10^4 lignes contenant chacune une valeur, cela représente 10^8 vérifications de lignes.

Algorithme

Définissez pos[r] = 0 pour chaque ligne et comptez les valeurs, N.
Répétez N fois : examinez chaque ligne dont pos[r] est encore à l’intérieur et retenez la ligne dont la tête est la plus petite.
Ajoutez cette tête au résultat et incrémentez de 1 le pos de cette ligne.
Renvoyez le résultat.

def mergeKLists(lists):
    pos = [0] * len(lists)  # pos[r]: index of the first unused value in row r
    total = sum(len(row) for row in lists)
    merged = []
    for _ in range(total):
        best = -1  # the row whose head is the smallest so far
        for r in range(len(lists)):
            if pos[r] < len(lists[r]) and (best == -1 or lists[r][pos[r]] < lists[best][pos[best]]):
                best = r
        merged.append(lists[best][pos[best]])
        pos[best] += 1
    return merged

Tas min des k têtes

Intuition

Après chaque extraction, une seule tête change, et pourtant le balayage relit les k éléments. Un tas min place la plus petite valeur au sommet. Associe chaque tête à sa ligne : après avoir extrait (value, row), tu sais quelle est la prochaine valeur de cette ligne à insérer. Le tas contient toujours une entrée par ligne ayant encore des valeurs ; son sommet est donc la plus petite valeur inutilisée.

Dans le premier exemple, le tas commence avec 2, 1 et 3. Extrais 1, insère 4. Extrais 2, insère 6. Extrais 3, insère 5. Extrais 4, insère 10. Extrais 5 : la troisième ligne est épuisée, donc rien n’est inséré. Extrais 6, insère 9, puis extrais 9 et 10.

Chaque valeur est insérée et extraite une seule fois, et le tas ne contient jamais plus de k entrées : 2N opérations en O(log k). Avec N = k = 10^4, cela représente moins de 3 × 10^5 étapes. Le tas utilise une mémoire de O(k).

Algorithme

Insérez (lists[r][0], r) pour chaque ligne r dans un min-tas ordonné par valeur.
Tant que le tas n’est pas vide, retirez la plus petite paire (value, r) et ajoutez value au résultat.
Si la ligne r a une valeur suivante, insérez-la avec r.
Renvoyez le résultat une fois que le tas est vide.

import heapq


def mergeKLists(lists):
    # The heap holds one (value, row) pair per row that still has values: that row's head.
    heap = [(row[0], r) for r, row in enumerate(lists)]
    heapq.heapify(heap)
    nxt = [1] * len(lists)  # nxt[r]: index of row r's next value, not yet in the heap
    merged = []
    while heap:
        value, r = heapq.heappop(heap)  # the smallest head of all rows
        merged.append(value)
        if nxt[r] < len(lists[r]):
            heapq.heappush(heap, (lists[r][nxt[r]], r))  # row r's new head takes its place
            nxt[r] += 1
    return merged

Pièges et cas limites

Empiler uniquement les valeurs. Après un retrait, tu ne peux pas savoir quelle ligne avancer. Stocke la ligne avec la valeur.
Utiliser par erreur un tas max. C++ priority_queue et Rust BinaryHeap placent la plus grande valeur au sommet ; utilise greater<> ou Reverse.
Empiler toutes les valeurs au départ. Le résultat reste trié, mais le tas atteint N entrées et le coût devient O(N log N).
Lire au-delà de la fin d’une ligne courte. Dans le premier exemple, la troisième ligne contient deux valeurs ; vérifie donc qu’il y a une valeur suivante avant de l’empiler.
Éliminer les doublons. Les trois 5 du deuxième exemple sont des valeurs distinctes, et elles doivent toutes figurer dans le résultat.

Questions fréquentes3

Quelle est la complexité temporelle de la fusion de k listes triées ?

Avec un tas min, la complexité est de O(N log k), où N est le nombre total de valeurs et k le nombre de listes. Chaque valeur est insérée puis extraite une fois, et le tas contient au plus k entrées. La mémoire supplémentaire est de O(k), en plus de la sortie.

Pourquoi ne pas rassembler toutes les valeurs et les trier ?

C’est exact et cela prend un temps de O(N log N). Cette méthode ne tient pas compte du fait que les listes sont déjà triées : elle paie donc log N pour chaque valeur, alors que le tas ne paie que log k, et elle nécessite de garder toutes les valeurs en mémoire en même temps. Le tas peut également fusionner des listes qui arrivent sous forme de flux.

Peux-tu fusionner k listes triées sans tas ?

Oui, grâce à la méthode diviser pour régner. Fusionnez les listes par paires avec la fusion de deux listes, puis fusionnez les résultats par paires, et ainsi de suite : log k étapes qui parcourent chacune chaque valeur une fois, soit O(N log k). Fusionner les listes les unes après les autres dans un résultat qui s’agrandit est plus lent, O(N·k), car les premières valeurs sont recopiées à chaque fusion.

def mergeKLists(lists):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

lists = [[2, 6, 9], [1, 4, 10], [3, 5]]

Résultat attendu

[1, 2, 3, 4, 5, 6, 9, 10]