Étant donné deux tableaux d'entiers, écrire une fonction pour calculer leur intersection. Chaque élément dans le résultat doit apparaître un nombre de fois égal au minimum de son occurrence dans les deux tableaux d'origine. L'ordre des éléments dans le résultat n'est pas important.

Exemple 1 :
Entrée : liste1 = [1,2,2,1], liste2 = [2,2]
Sortie : [2,2]

Exemple 2 :
Entrée : liste1 = [4,9,5], liste2 = [9,4,9,8,4]
Sortie : [4,9]

Voici une approche de base en Python. Elle utilise un dictionnaire pour compter les occurrences dans le premier tableau, puis parcourt le second tableau pour construire le résultat en décrémentant les compteurs.

def calculer_intersection(tableau_a, tableau_b):
    comptage = {}
    for valeur in tableau_a:
        comptage[valeur] = comptage.get(valeur, 0) + 1
    resultat = []
    for valeur in tableau_b:
        if valeur in comptage and comptage[valeur] > 0:
            resultat.append(valeur)
            comptage[valeur] -= 1
    return resultat

Cette méthode a une complexité temporelle de O(n + m), où n et m sont les tailles des deux tableaux. Une autre technique consiste à trier les tableaux et à utiliser deux pointeurs pour parcourir simultanément les listes triées. Cela réduit la complexité temporelle à O(n log n + m log n) due au tri, mais peut être plus efficace si les tableaux sont déjà triés.

def intersection_par_tri(tableau_a, tableau_b):
    tableau_a.sort()
    tableau_b.sort()
    i, j = 0, 0
    resultat = []
    while i < len(tableau_a) and j < len(tableau_b):
        if tableau_a[i] == tableau_b[j]:
            resultat.append(tableau_a[i])
            i += 1
            j += 1
        elif tableau_a[i] < tableau_b[j]:
            i += 1
        else:
            j += 1
    return resultat

Pour des tableaux de tailles très différentes, il peut être avantageux de parcourir le plus court et de vérifier les éléments dans le plus long à l'aide d'une table de hachage. Dans le cas où la mémoire est limitée et que le second tableau est stocké sur disque, une approche par blocs ou l'utilisation de structures de données extérieures comme des fichiers temporaires peut être envisagée. L'utilisation d'un ensemble (set) élimine les doublons, donc pour obtenir l'intersection avec comptage, il faut combiner l'intersection d'ensembles avec des compteurs individuels.

def intersection_par_ensemble(tableau_a, tableau_b):
    elements_communs = set(tableau_a) & set(tableau_b)
    resultat = []
    for elem in elements_communs:
        occ_min = min(tableau_a.count(elem), tableau_b.count(elem))
        resultat.extend([elem] * occ_min)
    return resultat

Cette méthode est concise mais moins efficace pour les grands tableaux en raison des appels répétés à la méthode count(). En pratique, la première approche par dictionnaire est souvent préférée pour son équilibre entre performance et lisibilité.