Merge Sorted Array

Q: Quelle est la complexité temporelle de la fusion de deux tableaux triés ?

Avec deux pointeurs, la complexité est de O(m + n) , où m et n sont les deux longueurs. À chaque étape, une valeur est placée, et aucune valeur n’est examinée deux fois. La concaténation puis le tri coûtent plutôt O((m + n) log(m + n)) .

Q: Comment fusionner deux tableaux triés sur place ?

Lorsque le premier tableau a de la place à la fin pour les deux, remplis-le en partant de la fin. Compare les plus grandes valeurs restantes des deux tableaux, écris la plus grande dans le dernier emplacement libre, puis avance d’un cran vers la gauche. En écrivant depuis la fin, tu n’écrases jamais une valeur du premier tableau qui n’a pas encore été placée, donc aucun deuxième tableau n’est nécessaire.

Q: La fusion de deux tableaux triés est-elle la même chose que l’étape de fusion du tri par fusion ?

Oui. Le tri fusion divise un tableau en deux moitiés, trie chaque moitié, puis réunit les deux moitiés triées à l’aide exactement de cette boucle à deux pointeurs. Prendre la valeur de gauche en cas d’égalité conserve les valeurs égales dans leur ordre d’origine, ce qui rend le tri fusion stable.

Q: Pourquoi ne pas concaténer les tableaux et appeler sort ?

Cette solution donne la bonne réponse et, en pratique, elle est souvent rapide. Mais elle ne tient pas compte du fait que les entrées sont déjà triées et coûte un facteur log supplémentaire. En entretien, la fusion à deux pointeurs est la réponse attendue, car elle montre que tu sais exploiter l’ordre qui t’a été donné.

FacileDeux pointeurs Tri

+10

Vous recevez deux tableaux d’entiers, nums1 et nums2. Chacun est déjà trié par ordre croissant au sens large. Renvoyez un seul tableau contenant toutes les valeurs des deux tableaux, également par ordre croissant au sens large. Une valeur présente dans les deux tableaux apparaît dans le résultat autant de fois qu’elle apparaît au total.

Fonction

merge(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: le premier tableau trié
nums2integer-array: le deuxième tableau trié
Renvoieinteger-array: toutes les valeurs des deux tableaux dans un seul tableau trié, de longueur nums1.length + nums2.length

Contraintes

1 ≤ nums1.length, nums2.length ≤ 2000
-10⁵ ≤ nums1[i], nums2[j] ≤ 10⁵
nums1 et nums2 sont chacun triés par ordre non décroissant.

Exemples

Entrée: nums1 = [1, 4, 9]nums2 = [2, 3, 10]
Sortie: [1, 2, 3, 4, 9, 10]
Explication: Lisez les deux premiers éléments et gardez le plus petit : 1, puis 2 et 3 de nums2, puis 4 et 9 de nums1, et enfin 10. Le résultat contient les six valeurs.

Entrée: nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
Sortie: [-5, 0, 0, 0, 6, 8]
Explication: Le 0 apparaît deux fois dans nums1 et une fois dans nums2, le résultat contient donc trois 0. Le -5 est plus petit que tous les éléments de nums2 et vient en premier.

+13 tests cachés à la soumission

Pour aller plus loin

Peux-tu fusionner k tableaux triés contenant au total N valeurs, en un temps de O(N log k) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Concaténer les tableaux et les trier donne la bonne réponse, mais cela ne tient pas compte du fait que les deux moitiés sont déjà triées. La plus petite valeur restante est toujours au début de l’un des deux tableaux. Gardez un index pour chaque tableau, prenez à chaque étape la plus petite des deux valeurs en tête, et un seul parcours suffit à construire le résultat. C’est l’étape de fusion du tri fusion.

Concaténer et trier

Intuition

Placez chaque valeur de nums1 et chaque valeur de nums2 dans un seul tableau, puis triez-le. Le résultat contient les bonnes valeurs, chacune autant de fois qu’elle apparaissait, dans le bon ordre.

Pour [1, 4, 9] et [2, 3, 10], le tableau concaténé est [1, 4, 9, 2, 3, 10], et le tri donne [1, 2, 3, 4, 9, 10].

Avec m valeurs dans nums1 et n dans nums2, un tri général coûte O((m + n) log(m + n)). Cette méthode fonctionne et est suffisamment rapide pour ces limites, mais elle n’exploite pas l’ordre de tri fourni. L’approche suivante le fait et supprime le facteur log.

Algorithme

Crée un tableau avec les valeurs de nums1 suivies de celles de nums2.
Trie-le par ordre numérique croissant.
Retourne-le.

def merge(nums1, nums2):
    return sorted(nums1 + nums2)

Deux pointeurs, un par tableau

Intuition

Gardez un indice i dans nums1 et j dans nums2, tous deux initialisés à 0. Tout ce qui précède i et j se trouve déjà dans le résultat. La plus petite valeur qui n’a pas encore été utilisée est nums1[i] ou nums2[j], car chaque tableau est trié et ses valeurs restantes ne peuvent être que plus grandes. Ajoutez la plus petite et avancez l’indice correspondant.

Avec [1, 4, 9] et [2, 3, 10] : 1 est plus petit que 2, puis 2 est plus petit que 4, 3 est plus petit que 4, 4 est plus petit que 10, et 9 est plus petit que 10. À présent, tous les éléments de nums1 ont été utilisés, donc le reste de nums2, c’est-à-dire [10], est copié tel quel. Le résultat est [1, 2, 3, 4, 9, 10].

Chaque étape écrit une valeur, donc la boucle s’exécute m + n fois : complexité temporelle O(m + n). Le tableau résultat est le seul espace mémoire supplémentaire.

Algorithme

Définis i et j à 0 et crée un résultat vide.
Tant que les deux tableaux contiennent encore des valeurs, compare nums1[i] à nums2[j].
Ajoute le plus petit et avance son index. En cas d’égalité, prends nums1[i].
Quand un tableau est épuisé, ajoute ce qui reste dans l’autre.
Renvoie le résultat.

def merge(nums1, nums2):
    result = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    # one array is used up; the rest of the other is already sorted
    result.extend(nums1[i:])
    result.extend(nums2[j:])
    return result

Pièges et cas limites

La plupart des bogues apparaissent au moment où un tableau arrive à la fin, ou dans la façon dont les valeurs sont comparées.

Arrêter la boucle dès qu’un tableau est épuisé et oublier le reste de l’autre. Avec [1, 2, 3] et [4, 5, 6], la boucle se termine après 1, 2 et 3, et il faut encore copier 4, 5 et 6.
Lire nums1[i] après que i a atteint la fin. Vérifiez les deux indices avant de comparer.
Éliminer les doublons. [0, 0] et [0] fusionnent en [0, 0, 0], et non en [0].
En JavaScript et TypeScript, sort() sans comparateur trie les nombres comme du texte. Ainsi, [-5, 10, 9] est trié en [-5, 10, 9]. Passez (a, b) => a - b.
En Lua et R, les tableaux commencent à 1, donc les deux indices commencent à 1 et les limites utilisent <=.

Questions fréquentes4

Quelle est la complexité temporelle de la fusion de deux tableaux triés ?

Avec deux pointeurs, la complexité est de O(m + n), où m et n sont les deux longueurs. À chaque étape, une valeur est placée, et aucune valeur n’est examinée deux fois. La concaténation puis le tri coûtent plutôt O((m + n) log(m + n)).

Comment fusionner deux tableaux triés sur place ?

Lorsque le premier tableau a de la place à la fin pour les deux, remplis-le en partant de la fin. Compare les plus grandes valeurs restantes des deux tableaux, écris la plus grande dans le dernier emplacement libre, puis avance d’un cran vers la gauche. En écrivant depuis la fin, tu n’écrases jamais une valeur du premier tableau qui n’a pas encore été placée, donc aucun deuxième tableau n’est nécessaire.

La fusion de deux tableaux triés est-elle la même chose que l’étape de fusion du tri par fusion ?

Oui. Le tri fusion divise un tableau en deux moitiés, trie chaque moitié, puis réunit les deux moitiés triées à l’aide exactement de cette boucle à deux pointeurs. Prendre la valeur de gauche en cas d’égalité conserve les valeurs égales dans leur ordre d’origine, ce qui rend le tri fusion stable.

Pourquoi ne pas concaténer les tableaux et appeler sort ?

Cette solution donne la bonne réponse et, en pratique, elle est souvent rapide. Mais elle ne tient pas compte du fait que les entrées sont déjà triées et coûte un facteur log supplémentaire. En entretien, la fusion à deux pointeurs est la réponse attendue, car elle montre que tu sais exploiter l’ordre qui t’a été donné.

Python

def merge(nums1, nums2):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums1 = [1, 4, 9]
nums2 = [2, 3, 10]

Attendu

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