Intersection of Two Arrays

+10

Tu reçois deux tableaux d’entiers, nums1 et nums2. Renvoie toutes les valeurs qui apparaissent dans les deux tableaux, triées par ordre croissant. Chaque valeur commune apparaît une seule fois dans la réponse, quel que soit le nombre de fois où elle se répète dans l’un ou l’autre tableau.

Fonction

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

nums1integer-array: la première liste d’entiers
nums2integer-array: la deuxième liste d’entiers
Renvoieinteger-array: les valeurs présentes dans les deux listes, chacune une seule fois, par ordre croissant

Contraintes

1 ≤ nums1.length, nums2.length ≤ 5000
-10⁵ ≤ nums1[i], nums2[i] ≤ 10⁵
Au moins une valeur apparaît dans les deux tableaux.

Exemples

Entrée: nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
Sortie: [4, 6]
Explication: 4 et 6 se trouvent dans les deux tableaux. 4 apparaît deux fois dans nums2, mais n’est répertorié qu’une seule fois, et 2 et 9 n’apparaissent jamais dans nums2.

Entrée: nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
Sortie: [-3, 7]
Explication: -3 et 7 sont présents dans les deux tableaux. Par ordre croissant, -3 vient en premier, même si 7 vient en premier dans nums2.

+16 tests cachés à la soumission

Pour aller plus loin

Et si nums1 contenait 10 valeurs et nums2 un million de valeurs, déjà triées ? Quelle approche choisirais-tu, et la recherche binaire peut-elle être plus efficace qu’un parcours complet ?

Indices

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

0 sur 3 ouverts

Solution

Deux détails déterminent ce problème : une valeur qui apparaît des deux côtés doit tout de même figurer une seule fois dans la réponse, et la réponse doit être triée. Comparer chaque paire fonctionne, mais nécessite n × m comparaisons, soit 2.5 × 10^7 lorsque les deux tableaux contiennent 5000 valeurs. Trier les deux tableaux permet à deux pointeurs de parcourir les valeurs communes dans l’ordre, et un ensemble de hachage contenant un des tableaux permet de répondre à la question « cette valeur se trouve-t-elle dans nums1 ? » en temps constant.

Comparez chaque paire

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Parcours chaque valeur de nums1 et cherche-la dans nums2. Arrête la recherche à la première correspondance et ignore une valeur qui figure déjà dans la réponse, de sorte que [8, 8, 8, 8] comparé à [8, 8] donne un seul 8, et non quatre. Trie la réponse à la fin.

C’est correct, car une valeur est ajoutée à la réponse exactement lorsqu’une de ses occurrences dans nums1 trouve une correspondance dans nums2, et l’ignorer évite de l’ajouter deux fois.

C’est lent, car chaque valeur de nums1 peut nécessiter de parcourir entièrement nums2. Avec 5000 valeurs dans chaque tableau, cela représente jusqu’à 2.5 × 10^7 comparaisons, et dans les grands tests, la plupart des valeurs ne trouvent aucune correspondance, donc la plupart des recherches vont jusqu’au bout.

Algorithme

Commencez avec une liste de réponses vide.
Pour chaque valeur a dans nums1, ignorez-la si elle se trouve déjà dans la réponse.
Sinon, parcourez nums2 ; à la première valeur égale à a, ajoutez a à la réponse et arrêtez le parcours.
Triez la réponse par ordre croissant et renvoyez-la.

def intersection(nums1, nums2):
    result = []
    for a in nums1:
        if a in result:
            continue
        # Look for a anywhere in nums2.
        for b in nums2:
            if a == b:
                result.append(a)
                break
    result.sort()
    return result

Trier les deux, puis parcourir avec deux pointeurs

Intuition

Une fois trié, l’exemple 1 devient [2, 2, 4, 6, 9] et [1, 4, 4, 6]. Place le pointeur i au début du premier tableau et j au début du second. Le pointeur sur la plus petite valeur avance : cette valeur ne peut correspondre à aucune valeur suivante de l’autre tableau, où toutes les valeurs sont au moins aussi grandes. Quand les deux pointeurs voient la même valeur, elle est commune : ajoute-la et avance les deux pointeurs.

Dans l’exemple : 2 > 1 fait avancer j, les deux 2 sont plus petits que 4 et font avancer i, 4 = 4 ajoute 4, le second 4 est plus petit que 6 et fait avancer j, et 6 = 6 ajoute 6. Une valeur présente plusieurs fois des deux côtés, comme 2 dans [2, 2, 3] et [2, 2], correspond plusieurs fois ; la comparer à la dernière valeur ajoutée permet de n’en garder qu’une copie. Le résultat est trié sans étape supplémentaire.

Le tri coûte O(n log n + m log m), et le parcours coûte O(n + m), car chaque étape fait avancer au moins un pointeur. La plupart des versions trient des copies, ce qui coûte O(n + m) en mémoire. Si tu peux réordonner les entrées, trie-les sur place, comme le fait le code C, et la seule mémoire supplémentaire est celle de la réponse.

Algorithme

Triez les deux tableaux.
Définissez i = 0 et j = 0.
Tant que les deux pointeurs se trouvent dans leurs tableaux, déplacez le pointeur correspondant à la plus petite valeur.
En cas de valeurs égales, ajoutez la valeur sauf si elle est égale à la dernière valeur ajoutée, puis déplacez les deux pointeurs.
Retournez la réponse.

def intersection(nums1, nums2):
    a = sorted(nums1)
    b = sorted(nums2)
    i, j = 0, 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            i += 1
        elif a[i] > b[j]:
            j += 1
        else:
            # A shared value: keep it once, even if it repeats.
            if not result or result[-1] != a[i]:
                result.append(a[i])
            i += 1
            j += 1
    return result

Ensemble de hachage du premier tableau

Intuition

Place chaque valeur de nums1 dans un ensemble de hachage. Dans l’exemple 1, l’ensemble est {6, 2, 9, 4} : le 2 répété est éliminé lors de l’insertion. Parcours ensuite nums2 et interroge l’ensemble pour chaque valeur en temps constant. Le premier 4 s’y trouve, il est donc ajouté à la réponse. Le second 4 ne doit pas y être ajouté : supprime une valeur de l’ensemble dès qu’elle correspond. 1 ne s’y trouve pas, contrairement à 6, ce qui donne [4, 6].

La suppression lors d’une correspondance permet de ne conserver chaque valeur qu’une seule fois : après sa première correspondance, une valeur disparaît de l’ensemble, donc les copies suivantes dans nums2 n’y trouvent rien. Chaque valeur ajoutée figure dans les deux tableaux, et chaque valeur commune est ajoutée à l’arrivée de sa première occurrence dans nums2.

La construction de l’ensemble et le parcours prennent en moyenne O(n + m). La réponse est produite dans l’ordre de nums2, alors trie-la à la fin ; elle contient k ≤ min(n, m) valeurs, ce qui coûte O(k log k). C n’a pas d’ensemble intégré, le code C utilise donc un tableau de drapeaux indexé par value + 10^5, ce qui fonctionne puisque les valeurs sont bornées.

Algorithme

Crée un ensemble de hachage first à partir de nums1.
Pour chaque valeur de nums2, si elle se trouve dans first, ajoute-la à la réponse et supprime-la de first.
Trie la réponse par ordre croissant.
Retourne-la.

def intersection(nums1, nums2):
    first = set(nums1)
    result = []
    for num in nums2:
        if num in first:
            result.append(num)
            # Remove it so a repeat in nums2 is not added twice.
            first.remove(num)
    result.sort()
    return result

Pièges et cas limites

La plupart des mauvaises réponses ici sont dues aux valeurs répétées et à l’ordre du résultat.

Ajouter une valeur chaque fois qu’elle correspond. [2, 2, 3, 3, 3] et [3, 2, 2] ont deux valeurs en commun, donc la réponse est [2, 3], et non [3, 2, 2].
Renvoyer les valeurs dans l’ordre où vous les avez trouvées. Le parcours de l’ensemble de hachage suit nums2, donc [7, -3] doit quand même être trié en [-3, 7].
Trier les nombres comme du texte. En JavaScript, sort() sans comparateur compare les chaînes, donc [100000, 99] reste dans cet ordre. Passez (x, y) => x - y.
Utiliser une intersection d’ensembles et oublier l’ordre. set(nums1) & set(nums2) en Python trouve les bonnes valeurs dans un ordre quelconque ; enveloppez-la dans sorted.
Indexer un tableau de drapeaux avec la valeur brute. -3 n’est pas un indice valide ; décalez d’abord chaque valeur de 10^5.

Questions fréquentes4

Quelle est la complexité temporelle de l’intersection de deux tableaux ?

Avec un ensemble de hachage, trouver les valeurs communes prend O(n + m) en moyenne, et trier les k valeurs de la réponse ajoute O(k log k) ; l’ensemble utilise O(n) d’espace. Trier les deux tableaux et les parcourir avec deux pointeurs prend O(n log n + m log m). Comparer chaque paire prend O(n × m).

Faut-il utiliser un ensemble de hachage ou deux pointeurs ?

Utilisez l’ensemble de hachage lorsque les tableaux ne sont pas triés et que la mémoire est disponible : c’est la méthode qui demande le moins de travail. Utilisez deux pointeurs lorsque les deux tableaux sont déjà triés, ou lorsque la mémoire est limitée et que vous pouvez les trier sur place. Le parcours ne nécessite aucun ensemble et produit le résultat dans l’ordre.

Comment conserver les valeurs répétées dans l’intersection ?

Si une valeur doit apparaître autant de fois qu’elle apparaît dans les deux tableaux, de sorte que [3, 1, 3, 3] et [3, 3] donnent [3, 3], remplace l’ensemble par une table de comptage. Compte les valeurs de nums1 et, pour chaque valeur de nums2 dont le compte est supérieur à zéro, ajoute-la et diminue son compte. Dans le parcours à deux pointeurs, supprime la vérification de la dernière valeur ajoutée.

Comment trouver l’intersection lorsqu’un tableau est trop volumineux pour être chargé en mémoire ?

Construisez l’ensemble de hachage à partir du tableau qui tient en mémoire et lisez le plus grand par morceaux, en vérifiant chaque valeur par rapport à l’ensemble et en la supprimant en cas de correspondance. La mémoire utilisée reste de la taille du plus petit tableau. Si aucun des deux tableaux ne tient en mémoire, triez les deux sur disque et parcourez les fichiers triés à l’aide de deux pointeurs.

Python

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

Cas de test

Cas 1

Cas 2

Entrée

nums1 = [6, 2, 9, 2, 4]
nums2 = [4, 4, 1, 6]

Attendu

[4, 6]

Intersection of Two Arrays

Fonction

Contraintes

Exemples

Indices

Solution

Comparez chaque paire

Trier les deux, puis parcourir avec deux pointeurs

Ensemble de hachage du premier tableau

Pièges et cas limites

Questions fréquentes4

Problèmes similaires