Merge k Sorted Lists

Q: Quelle est la complexité temporelle de Merge k Sorted Lists ?

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 et retirée une fois, et le tas contient au plus k entrées, donc chaque opération coûte O(log k) . La mémoire supplémentaire est de O(k) , en plus de la sortie.

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

C’est correct et cela prend un temps de O(N log N) , ce qui convient pour de petites entrées. 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 d’avoir toutes les valeurs en mémoire en même temps. Le tas peut aussi fusionner des listes qui arrivent sous forme de flux, ce que le tri ne peut pas faire.

DifficileTas Liste chaînée

+10

Tu reçois 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.

Fusionne-les en une seule liste contenant toutes les valeurs de toutes les lignes, triées par ordre non décroissant, puis retourne-la. Une valeur qui apparaît plusieurs fois, dans une seule ligne ou dans plusieurs, 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: toutes les valeurs de toutes les lignes, dans une seule liste triée

Contraintes

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length, et toutes les lignes contiennent au total au plus 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: La plus petite valeur au total est 1, la première valeur de la deuxième ligne. Après elle, les lignes commencent par 2, 4 et 3 ; 2 vient donc ensuite, et ainsi de suite. La troisième ligne s’arrête après 5, ce qui laisse 6, 9 et 10 à la fin.

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 est trié avant 0.

+14 tests cachés à la soumission

Pour aller plus loin

Trouvez le plus petit intervalle [a, b] qui contient au moins une valeur de chaque ligne. Le même tas des premiers éléments de chaque ligne, accompagné du plus grand premier élément rencontré jusqu’à présent, peut-il le trouver en O(N log k) ?

Solution

Chaque ligne est triée, donc la plus petite valeur qui n’a pas encore été utilisée est toujours la première valeur inutilisée d’une ligne. Tout le problème consiste à trouver le plus petit de k débuts de ligne, N fois de suite, où N est le nombre de valeurs. Parcourir tous les débuts coûte k étapes par valeur. Un tas min maintient les débuts en ordre et fournit le plus petit en O(log k), ce qui réduit le coût total de O(N·k) à O(N log k). Dans la forme classique, chaque liste est une liste chaînée ; ici, chaque ligne est un tableau, et un index par ligne remplit le rôle du pointeur de nœud.

Comparez toutes les têtes k pour chaque valeur

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Conservez un index par ligne, pos[r], pointant vers la première valeur de la ligne r que vous n’avez pas encore utilisée : la tête de la ligne. La plus petite valeur inutilisée doit nécessairement être l’une de ces têtes. Dans la ligne r, chaque valeur inutilisée se trouve à la position pos[r] ou après, et la ligne est triée : aucune d’elles n’est donc inférieure à la tête.

Il suffit donc de chercher la plus petite tête parmi toutes les lignes qui contiennent encore des valeurs, de l’ajouter, puis d’avancer l’index de cette ligne d’une position. Répétez jusqu’à ce que les N valeurs soient toutes sorties. C’est l’étape de fusion du tri fusion, étendue de deux listes à k.

Dans le premier exemple, les têtes sont au départ 2, 1 et 3 : 1 sort donc en premier et la tête de la deuxième ligne devient 4. Vient ensuite 2 (têtes 2, 4, 3), puis 3 (têtes 6, 4, 3), puis 4, puis 5, ce qui vide la troisième ligne. Lors des trois dernières étapes, on compare uniquement 6 et 10, puis 9 et 10, puis 10 seul.

Le coût est de k comparaisons pour chacune des N valeurs. Avec 10^4 lignes contenant une valeur chacune, cela représente 10^8 comparaisons. C, Java ou JavaScript les traitent en moins d’une seconde, mais Python a besoin de plus de dix secondes, et doubler à la fois N et k rend chaque langage quatre fois plus lent. Le gaspillage apparaît dans la trace : après chaque sélection, une seule tête a changé, et pourtant l’étape suivante relit à nouveau les k têtes.

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 toujours à l’intérieur et mémorisez la ligne dont la tête est la plus petite.
Ajoutez cette tête au résultat et ajoutez 1 à 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

Le parcours relit les k têtes pour trouver la plus petite, alors qu’une seule tête a changé depuis le tour précédent. Un tas min est fait exactement pour cela : il contient un ensemble de nombres avec le plus petit au sommet, et le retrait du sommet comme l’ajout d’un nombre coûtent tous deux O(log size).

Place la première valeur de chaque ligne dans le tas, en associant à chacune son numéro de ligne. Puis répète : retire la plus petite paire (value, row), ajoute value au résultat et, si cette ligne contient une autre valeur, ajoute-la au tas avec la même étiquette. Le tas contient toujours exactement une entrée pour chaque ligne qui contient encore des valeurs : sa tête. Le sommet est donc la plus petite valeur inutilisée de l’ensemble. C’est la règle du parcours, mais appliquée plus rapidement.

Suivons le premier exemple, avec des lignes numérotées à partir de 0. Le tas commence avec 2 (ligne 0), 1 (ligne 1) et 3 (ligne 2). Retire 1 et ajoute la valeur suivante de la ligne 1, 4. Retire 2 et ajoute 6 de la ligne 0. Retire 3 et ajoute 5 de la ligne 2. Retire 4 et ajoute 10. Retire 5 : la ligne 2 est épuisée, donc rien n’est ajouté et le tas ne contient plus que 6 et 10. Retire 6 et ajoute 9. Retire 9, puis 10. Le résultat est [1, 2, 3, 4, 5, 6, 9, 10].

Chaque valeur entre une fois dans le tas et en sort une fois, et le tas ne contient jamais plus de k entrées. Chacune de ces 2N opérations coûte donc O(log k). Avec N = k = 10^4, cela représente environ 2 × 10^4 × 14, soit moins de 3 × 10^5 étapes, contre 10^8 pour le parcours. Le tas utilise O(k) mémoire, jamais O(N), car il conserve une tête par ligne et non les valeurs qui la suivent.

Plusieurs versions construisent le tas à la main, dans un tableau de numéros de ligne ordonnés selon la tête de chaque ligne, avec les enfants de l’emplacement i aux emplacements 2i+1 et 2i+2 (aux emplacements 2i et 2i+1 en Lua et R, qui commencent à compter à partir de 1). Cela permet aussi d’économiser du travail : après avoir retiré la tête de la ligne au sommet, la valeur suivante de cette ligne n’est pas plus petite. La ligne reste donc au sommet et descend d’une seule étape, au lieu de procéder à un retrait suivi d’un ajout.

Algorithme

Insérez (lists[r][0], r) pour chaque ligne r dans un tas min 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

La logique du tas est courte. La plupart des bogues viennent des éléments placés dans le tas et de l’ordre utilisé.

Oublier l’origine d’une valeur. Si le tas ne contient que des valeurs, vous ne pouvez pas savoir quelle ligne avancer après une extraction. Stockez la ligne avec la valeur.
Utiliser par erreur un tas max. En C++, priority_queue et en Rust, BinaryHeap placent la plus grande valeur en tête ; utilisez greater<> ou Reverse. En Java, PriorityQueue et en Python, heapq placent déjà la plus petite valeur en tête.
Les égalités dans heapq en Python. Lorsque deux valeurs sont égales, la comparaison des tuples passe au deuxième élément. Un numéro de ligne se compare sans problème, mais pas un nœud de liste chaînée, et la version classique plante lorsque des valeurs sont égales. Placez un numéro de ligne ou un compteur en deuxième position.
Insérer toutes les valeurs dès le départ. Le tri reste correct, mais le tas atteint N éléments et le travail passe à O(N log N). Gardez une seule tête par ligne.
Lire au-delà de la fin d’une ligne courte. Les lignes ont des longueurs différentes ; vérifiez donc qu’une ligne a une valeur suivante avant de l’insérer.
Éliminer les doublons. Les valeurs égales provenant de lignes différentes sont des valeurs distinctes, et elles doivent toutes figurer dans le résultat.

Questions fréquentes4

Quelle est la complexité temporelle de Merge k Sorted Lists ?

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 et retirée une fois, et le tas contient au plus k entrées, donc chaque opération coûte O(log k). La mémoire supplémentaire est de O(k), en plus de la sortie.

Pourquoi ne pas regrouper toutes les valeurs et les trier ?

C’est correct et cela prend un temps de O(N log N), ce qui convient pour de petites entrées. 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 d’avoir toutes les valeurs en mémoire en même temps. Le tas peut aussi fusionner des listes qui arrivent sous forme de flux, ce que le tri ne peut pas faire.

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

Oui, en procédant par 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. Il y a log k étapes et chaque étape parcourt chaque valeur une fois, donc la complexité est également de O(N log k). Fusionner les listes l’une après l’autre dans un résultat qui grandit est plus lent : les premières valeurs sont recopiées à chaque fusion, ce qui donne une complexité de O(N·k).

Pourquoi le tas n’a-t-il besoin que de la tête de chaque liste ?

Chaque liste est triée, donc sa première valeur non utilisée est la plus petite valeur qui lui reste. La plus petite valeur parmi toutes les listes est donc la plus petite de leurs têtes, et aucune valeur plus loin dans une liste ne peut la battre. Lorsqu'une tête est retirée, la valeur suivante de la même liste devient la tête de cette liste et prend sa place dans le tas.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

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