Trouver les nombres communs entre deux listes

Profitons en pour expliquer ici un petit algorithme qui permet de trouver rapidement tous les nombres communs entre deux listes. Pour qu'il fonctionne, les listes doivent posséder le même nombre d'éléments et ces derniers doivent être triés par ordre croissant.
  1. Créer un index sur le premier nombre de chaque liste.
  1. Si les nombres pointés par les index sont identiques, ajouter la valeur commune au résultat et avancer d'un cran les deux index.
  1. Sinon, si le nombre pointé dans la première liste est inférieur à celui pointé dans la seconde, avancer uniquement l'index de la première liste.
  1. Sinon, avancer uniquement l'index de la seconde liste.
  1. Maintenant, si aucun index n'est sorti de sa liste, retourner à l'étape 2.
  1. C'est fini.
def common(list1, list2):
    n = len(list1)
    x, y = 0, 0
    resultat = []
    while x < n and y < n:
        if liste1[x] == liste2[y]:
            resultat.append(liste1[x])
            x += 1
            y += 1
        elif liste1[x] < liste2[y]:
            x += 1
        else:
            y += 1
    return resultat
Pages : 1 2 3 4 5 6 7 8 9 10
Tétraèdre Magique
18 février 2013
Sommaire général