Find the Duplicate Number

Q: Quelle est la complexité temporelle de Find the Duplicate Number ?

La détection de cycle de Floyd s’exécute en O(n) avec O(1) de mémoire supplémentaire : chacune de ses deux phases suit au plus quelques multiples de n liens. La recherche binaire sur les valeurs prend un temps de O(n log n) et utilise O(1) de mémoire. Comparer chaque paire a une complexité de O(n²) .

Q: Pourquoi ne pas utiliser un ensemble de hachage ou trier le tableau ?

Les deux trouvent la réponse en O(n) ou en O(n log n) , et dans un vrai programme, les deux conviendraient. La tâche les interdit volontairement : un ensemble de hachage utilise une mémoire supplémentaire de O(n) , et le tri modifie nums ou nécessite une copie complète. Ce sont ces restrictions qui vous orientent vers la représentation en cycles.

MoyenPointeurs rapide et lent Recherche binaire

+10

Vous recevez un tableau nums de n+1 entiers, chacun compris entre 1 et n. Une seule valeur apparaît plusieurs fois, éventuellement un grand nombre de fois, et vous renvoyez cette valeur.

Résolvez le problème sans modifier nums et en utilisant uniquement une quantité constante de mémoire supplémentaire.

Fonction

findDuplicate(nums: integer-array) → integer

numsinteger-array: n+1 entiers, chacun compris entre 1 et n
Renvoieinteger: la valeur qui apparaît plus d’une fois

Contraintes

1 ≤ n ≤ 10⁴
nums.length == n+1
1 ≤ nums[i] ≤ n
Une seule valeur apparaît deux fois ou plus ; toutes les autres valeurs apparaissent au plus une fois.

Exemples

Entrée: nums = [2, 5, 1, 3, 5, 4]
Sortie: 5
Explication: Ici, n vaut 5, et 5 se trouve aux positions 1 et 4, donc la réponse est 5. Toutes les autres valeurs de 1 à 5 apparaissent une fois.

Pour aller plus loin

La recherche binaire sur les valeurs respecte les deux règles en un temps de O(n log n). Peux-tu les respecter en un temps de O(n) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Un ensemble de hachage ou un tri permet de trouver immédiatement le doublon, mais les deux enfreignent les règles : l’ensemble nécessite de la mémoire pour chaque valeur, et le tri modifie nums. La solution se trouve dans les nombres. Chaque valeur est comprise entre 1 et n, c’est donc aussi une position valide dans le tableau. Considérez chaque valeur comme un lien vers une autre position, et suivre les liens depuis la position 0 mène toujours à une boucle dont le point d’entrée est le doublon. Les pointeurs rapide et lent de Floyd trouvent ce point d’entrée avec deux entiers.

Comparez chaque paire

Correcte, mais ne termine pas sur les plus gros tests

Intuition

La valeur répétée se trouve à au moins deux positions i < j. Compare chaque position à toutes celles qui la suivent ; la première paire contenant des valeurs égales donne la réponse. Dans le premier exemple, la position 1 contient 5, et le parcours à partir de la position 2 trouve un autre 5 à la position 4.

Cette méthode respecte les deux règles : rien n’est écrit et les seules données mémorisées sont deux compteurs de boucle. Elle est lente, car elle compare des paires. Avec n+1 = 10,001 valeurs et les deux copies vers la fin, elle vérifie environ 5 × 10^7 paires.

Algorithme

Pour chaque position i, de 0 jusqu’à la fin :
Pour chaque position j après i, comparez nums[i] à nums[j].
Renvoyez nums[i] dès la première correspondance.

def findDuplicate(nums):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return nums[i]
    return -1  # unreachable: the input always holds a repeat

Recherche binaire sur la valeur

Intuition

Recherchez dans l’intervalle des valeurs, pas des positions. Choisissez un seuil m et comptez combien d’éléments de nums sont inférieurs ou égaux à m.

Si le doublon d est supérieur à m, les valeurs de 1 à m apparaissent chacune au plus une fois, donc le compte est au plus égal à m. Si d est inférieur ou égal à m, chaque valeur supérieure à m apparaît au plus une fois, donc au plus n-m éléments sont supérieurs à m et au moins m+1 sont inférieurs ou égaux à m. Le test « count > m » est donc faux pour tout m inférieur à d et vrai à partir de d. La recherche dichotomique trouve le premier m pour lequel le test devient vrai, et c’est d.

Dans le deuxième exemple, n vaut 4. Pour m = 2, les éléments 2 et 1 donnent un compte de 2, qui n’est pas supérieur à 2, donc la réponse est supérieure à 2. Pour m = 3, le compte est toujours de 2, donc la réponse est 4. À chaque étape, on lit le tableau entier une fois et on divise l’intervalle par deux, donc le travail est de O(n log n) : environ 14 parcours de 10,001 valeurs.

Algorithme

Définissez low = 1 et high = n, la longueur de nums moins un.
Tant que low < high, prenez mid à mi-chemin entre eux.
Comptez les éléments de nums qui sont inférieurs ou égaux à mid.
Si le compte est supérieur à mid, définissez high = mid ; sinon, définissez low = mid+1.
Renvoyez low.

def findDuplicate(nums):
    low, high = 1, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        # How many values fall in 1..mid?
        count = 0
        for x in nums:
            if x <= mid:
                count += 1
        if count > mid:
            high = mid      # 1..mid holds more values than it has room for
        else:
            low = mid + 1   # the repeat is above mid
    return low

Détection de cycle de Floyd sur les liens de valeurs

Intuition

Lisez le tableau comme un ensemble de liens : la position i pointe vers la position nums[i]. Chaque position de 0 à n possède exactement un lien sortant, et chaque lien aboutit quelque part entre 1 et n. Dans le premier exemple, les liens sont 0 → 2, 1 → 5, 2 → 1, 3 → 3, 4 → 5 et 5 → 4.

Partez de la position 0 et suivez les liens. Le parcours ne peut jamais s'arrêter, car chaque position possède un lien et il n'y a que n+1 positions ; il doit donc revenir à une position déjà visitée. À partir de là, il tourne indéfiniment. Le chemin est une queue suivie d'une boucle, en forme de lettre ρ. Dans le premier exemple, le parcours est 0, 2, 1, 5, 4, 5, 4, et ainsi de suite : la queue est 0, 2, 1 et la boucle est 5, 4. La position 3 pointe vers elle-même, mais le parcours ne l'atteint jamais, et cela ne pose aucun problème.

L'entrée de la boucle est le doublon. Le parcours entre deux fois en 5 depuis des endroits différents : une fois depuis la fin de la queue (position 1, car nums[1] vaut 5) et une fois depuis la fin de la boucle (position 4, car nums[4] vaut 5). Deux positions différentes contiennent la valeur 5, donc 5 se répète. La queue contient toujours la position 0, car aucune valeur n'est 0 et aucun lien ne pointe vers elle ; l'entrée a donc toujours ces deux chemins d'accès distincts. Une seule valeur se répète : l'entrée est donc cette valeur.

Trouvez maintenant l'entrée à l'aide de deux pointeurs, comme pour la détection d'un cycle dans une liste chaînée. Dans la phase 1, slow suit un lien par tour et fast en suit deux, jusqu'à ce qu'ils se trouvent sur la même position quelque part dans la boucle. Dans le premier exemple, ils se rencontrent en 4. Dans la phase 2, replacez slow en 0, laissez fast où il est et avancez les deux d'un lien par tour. Ils se rencontrent à l'entrée.

Pourquoi la phase 2 fonctionne : supposons que la queue comporte T liens jusqu'à l'entrée et que la boucle compte C positions. Lorsque les pointeurs se sont rencontrés, slow avait fait s pas et fast 2s. Ils se trouvaient au même endroit, donc les s pas supplémentaires de fast correspondaient à des tours complets de la boucle. Après T pas supplémentaires, slow atteint l'entrée depuis 0, et fast se trouve à l'endroit où se trouverait un parcours depuis 0 après s+T pas, puisque ses tours supplémentaires ne changent rien. Cela correspond à T pas jusqu'à l'entrée, plus s pas, soit un nombre entier de tours, ce qui le place lui aussi à l'entrée. Ils ne peuvent pas se rencontrer plus tôt, car slow se trouve encore sur la queue et fast ne quitte jamais la boucle. Dans le premier exemple, slow passe par 2, 1, 5 tandis que fast passe par 5, 4, 5 ; ils se rencontrent en 5 après T = 3 pas.

Chaque phase prend O(n) pas, les seules données mémorisées sont deux positions, et nums n'est jamais modifié.

Algorithme

Considérez chaque position i comme un nœud relié à la position nums[i], et placez les deux pointeurs à la position 0.
Phase 1 : déplacez slow vers nums[slow] et fast vers nums[nums[fast]] jusqu’à ce qu’ils soient égaux.
Phase 2 : replacez slow à 0.
Déplacez les deux pointeurs d’un lien à la fois, slow vers nums[slow] et fast vers nums[fast], jusqu’à ce qu’ils soient égaux.
Renvoyez cette position : c’est la valeur répétée.

def findDuplicate(nums):
    # Treat each index i as a node with one link, to nums[i].
    # Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    # Phase 2: restart one pointer at index 0 and move both one link at a time.
    # They meet at the cycle's entrance, the index two positions link to.
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

Pièges et cas limites

La plupart des mauvaises réponses viennent d’une confusion entre les positions et les valeurs, ou du fait d’arrêter la méthode de Floyd une phase trop tôt.

Retourner le point de rencontre de la phase 1. Il s’agit d’une position sur le cycle, pas nécessairement de son entrée. Dans le premier exemple, les pointeurs se rencontrent à 4, mais la réponse est 5.
Vérifier slow == fast avant le premier déplacement. Les deux commencent à 0, donc la boucle se termine immédiatement. Déplacez-les d’abord, puis comparez-les, ou placez-les à un et deux liens de l’avance.
Commencer le parcours à une position autre que 0. Aucun lien ne pointe vers la position 0, puisqu’aucune valeur n’est égale à 0, ce qui garantit une queue. Commencer à une autre position peut vous placer sur un cycle sans accès depuis l’extérieur, comme la position 3 dans le premier exemple, dont l’entrée ne prouve rien.
Supposer que le doublon apparaît exactement deux fois. L’astuce de la somme, total moins 1 + 2 + ... + n, donne 15 moins 10 = 5 dans le deuxième exemple, mais la réponse est 4. Il en va de même pour les astuces basées sur XOR.
Effectuer une recherche binaire sur les positions plutôt que sur les valeurs, ou tester count >= mid. Le nombre de valeurs inférieures ou égales à m est exactement m lorsqu’aucune valeur de 1 à m n’est répétée et qu’aucune ne manque ; seul > permet donc de distinguer les deux côtés.
Marquer les valeurs visitées en niant nums[x] ou en échangeant les valeurs pour les mettre à leur place. Ces deux méthodes fonctionnent, mais elles modifient toutes deux le tableau, ce que l’énoncé interdit.

Questions fréquentes3

Quelle est la complexité temporelle de Find the Duplicate Number ?

La détection de cycle de Floyd s’exécute en O(n) avec O(1) de mémoire supplémentaire : chacune de ses deux phases suit au plus quelques multiples de n liens. La recherche binaire sur les valeurs prend un temps de O(n log n) et utilise O(1) de mémoire. Comparer chaque paire a une complexité de O(n²).

Pourquoi la détection de cycle de Floyd trouve-t-elle le nombre en double ?

Si vous lisez chaque valeur comme un lien entre sa position et la position qu’elle désigne, le parcours à partir de la position 0 doit finir par entrer dans une boucle, car il ne s’arrête jamais et ne peut visiter que n+1 positions. La position où il entre dans la boucle est atteinte depuis deux positions différentes, l’une sur la queue et l’autre dans la boucle, donc deux entrées contiennent cette valeur. La méthode de Floyd trouve l’entrée d’une boucle à l’aide de deux pointeurs, elle trouve donc la valeur répétée.

Pourquoi ne pas utiliser un ensemble de hachage ou trier le tableau ?

Les deux trouvent la réponse en O(n) ou en O(n log n), et dans un vrai programme, les deux conviendraient. La tâche les interdit volontairement : un ensemble de hachage utilise une mémoire supplémentaire de O(n), et le tri modifie nums ou nécessite une copie complète. Ce sont ces restrictions qui vous orientent vers la représentation en cycles.

def findDuplicate(nums):
    # Écrivez le code ici

Test #1

Test #2

Argument

nums = [2, 5, 1, 3, 5, 4]

Résultat attendu

Find the Duplicate Number

Fonction

Contraintes

Exemples

Indices

Solution

Comparez chaque paire

Recherche binaire sur la valeur

Détection de cycle de Floyd sur les liens de valeurs

Pièges et cas limites

Questions fréquentes3

Problèmes similaires