Comment rechercher des doublons dans un tableau avec une complexité temporelle et spatiale optimale ?

Recherche de doublons avec une complexité temporelle et spatiale optimale

Introduction :
La tâche de détection des éléments en double dans un tableau est un problème courant en programmation. Même si les solutions utilisant des structures de données auxiliaires telles que les tables de hachage offrent une certaine simplicité, elles compromettent l'efficacité de l'espace. Cet article présente un algorithme ingénieux qui identifie les doublons en temps linéaire, O(n), tout en maintenant une consommation d'espace constante, O(1).

Énoncé du problème :
Étant donné un tableau de n éléments allant de 0 à n-1, où certains nombres peuvent apparaître plusieurs fois, trouvez les éléments en double dans le tableau.

Algorithme optimal :

// Iterate through the array
for i = 0 to n - 1:
    // Swap elements until A[A[i]] = A[i]
    while A[A[i]] != A[i]:
        swap(A[i], A[A[i]])
    end while

// Identify duplicates based on A[i] != i
for i = 0 to n - 1:
    if A[i] != i:
        print A[i]
    end if
end for

Insight :
L'algorithme exploite le fait que chaque élément du tableau doit idéalement résider à son index. Il utilise les éléments du tableau pour créer une permutation, garantissant que les éléments existants seront mappés à leurs indices corrects. La première boucle parcourt le tableau et garantit que chaque élément atteint son index prévu via des échanges.

Explication :
La première boucle permute le tableau de sorte que pour tout élément x, si il apparaît au moins une fois, une instance sera à l'index A[x]. Dans chaque swap, une entrée correspondant à un élément incorrect est corrigée, garantissant que le nombre total de swaps est limité par le nombre d'éléments, N-1.

La deuxième boucle identifie les doublons en imprimant l'index de chacun élément qui ne correspond pas à son index, indiquant son absence dans le tableau d'origine.

Conclusion :
Cet algorithme identifie efficacement les éléments en double dans un tableau en utilisant intelligemment le tableau d'entrée lui-même. Sa complexité temporelle O(n) et spatiale O(1) le rend adapté à un large éventail d'applications pratiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!