Maison > développement back-end > C++ > le corps du texte

Comment pouvons-nous trouver des doublons dans un tableau de nombres de 0 à n-1 dans le temps O(n) et l'espace O(1) ?

Linda Hamilton
Libérer: 2024-11-01 20:02:02
original
985 Les gens l'ont consulté

How can we find duplicates in an array of numbers from 0 to n-1 in O(n) time and O(1) space?

Trouver des doublons dans le temps O(n) et l'espace O(1) : une explication approfondie

Le problème posé consiste à identifier les doublons éléments dans un tableau contenant des nombres allant de 0 à n-1. Le défi consiste à y parvenir efficacement, dans une complexité temporelle O(n) et en utilisant uniquement un espace mémoire constant (O(1)).

La solution présentée utilise une technique ingénieuse qui ne nécessite aucune table de hachage ni aucune autre donnée supplémentaire. structures. Au lieu de cela, il exploite les valeurs du tableau lui-même pour identifier et marquer les éléments en double.

  1. Permutation du tableau :

    La boucle interne permute le tableau basé sur la logique suivante :

    while A[A[i]] != A[i]
        swap(A[i], A[A[i]])
    end while
    Copier après la connexion

    Cette étape de permutation garantit que si un élément x existe dans le tableau, au moins une de ses instances sera positionnée en A[x]. Ceci est crucial pour les étapes suivantes.

  2. Identification des doublons :

    La boucle externe inspecte chaque élément A[i] :

    for i := 0 to n - 1
        if A[i] != i then
            print A[i]
        end if
    end for
    Copier après la connexion

    Si A[i] != i, cela signifie que i n'est pas présent à sa juste place dans le tableau. Par conséquent, il s'agit d'un élément en double, et il est imprimé.

  3. Analyse de la complexité temporelle :

    La technique s'exécute en temps O(n) . La boucle imbriquée a une boucle externe qui itère n fois et une boucle interne qui effectue au plus n - 1 itérations (car chaque échange rapproche un élément de sa position correcte). Ainsi, le nombre total d'itérations est limité par n*(n - 1), qui est O(n^2), mais peut être simplifié en O(n) car n*(n - 1) = n^2 - n = n(n - 1) = n*n - n ≪ n*n = O(n^2) = O(n).

  4. Analyse de la complexité spatiale :

    L'algorithme utilise uniquement un espace constant , indépendamment de la taille de l'entrée. L'idée clé est que l'espace utilisé pour les permutations est déjà présent dans le tableau d'entrée. Aucune structure de stockage supplémentaire n'est requise.

  5. Remarques supplémentaires :

    • L'algorithme suppose que le tableau contient des entiers de 0 à n - 1.
    • La complexité temporelle reste la même, même en présence de doublons.
    • L'algorithme est efficace pour les tableaux de taille petite à moyenne. Pour les grands tableaux, des approches alternatives utilisant des structures de données telles que des tables de hachage peuvent être plus adaptées.

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!

source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers articles par auteur
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!