Algorithme de Roy-Floyd-Warshall appliqué à la recherche de doublons.

Concidérons un tableau de n éléments qui contient des éléments compris entre  1 et n-1, l’un de ces nombres apparaissant autant de fois.

Contraintes

Trouver l’un de ces nombres répétitifs en y appliquant un algorithme de complexité O(n)
Utiliser uniquement un espace mémoire constant.

Voici donc une approche basée sur l’algorithme de recherche de cycle de Roy-Floyd-Warhall.

Nous l’utilisons pour détecter une boucle dans une liste chaînée. L’idée est de considérer les éléments du tableau comme des nœuds de liste liés. Tout index particulier pointe vers la valeur de cet index.

Et nous verrons qu’il y a une boucle comme indiqué dans l’image ci-dessous.

En cas de doublon, deux index auront la même valeur et ils formeront un cycle comme dans l’image ci-dessous.

La liste liée formée pour l’exemple  serait:

4->2->3->5->4->1

Nous pouvons donc trouver le point d’entrée du cycle dans la liste chaînée: ce sera notre élément en double.

  1. Nous maintenons deux pointeurs rapides et lents
  2. Pour chaque étape, rapide se déplacera vers l’index qui est égal à arr [arr [rapide]] (deux sauts à la fois) et lent se déplacera vers l’index arr [lent] (une étape à la fois).
  3. Lorsque rapide == lent, cela signifie que nous sommes maintenant dans un cycle.
  4. Rapide et lent se rencontreront dans un cercle et le point d’entrée de ce cercle sera l’élément en double.
  5. Maintenant, nous devons trouver un point d’entrée, nous allons donc commencer par rapide= 0 et visiter une étape à la fois à la fois rapide et lent.
  6. Lorsque rapide == lent, ce sera le point d’entrée.
  7. Renvoyer le point d’entrée.
arr = [4,2,3,5,4,1]

def findDuplicate(arr):
    slow = arr[0]
    fast = arr[arr[0]]

    while(fast != slow):
        slow = arr[slow]
        fast = arr[arr[fast]]

    fast = 0
    while(fast!= slow):
        slow = arr[slow]
        fast = arr[fast]

    return slow

res = findDuplicate(arr)
print(res) // output: 4

Complexité temporelle: O(n)

Espace auxiliaire: O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *