Contains Duplicate

Q: Quelle est la complexité temporelle de Contains Duplicate ?

La solution utilisant un ensemble de hachage s’exécute en temps O(n) en moyenne et utilise un espace supplémentaire O(n) . Le tri préalable prend un temps O(n log n) et ne nécessite pas de tableau supplémentaire si tu peux réordonner l’entrée. Comparer chaque paire prend un temps O(n²) .

Q: Peux-tu résoudre Contains Duplicate sans espace supplémentaire ?

Oui, si tu as le droit de réordonner le tableau : trie-le sur place et compare chaque valeur avec sa voisine. Cela remplace l’ensemble en O(n) par un temps en O(n log n) . Sans réordonner le tableau et sans mémoire supplémentaire, la seule option restante est de vérifier les paires en O(n²) .

Q: Pourquoi un ensemble de hachage rend-il la vérification rapide ?

Un ensemble de hachage stocke les valeurs à l’aide de leur hachage ; vérifier s’il contient une valeur prend donc un temps constant en moyenne, au lieu de parcourir les éléments. Chaque élément nécessite une recherche et une insertion, ce qui rend le parcours complet linéaire.

Q: Comparer la taille de l’ensemble à la longueur du tableau est-il une solution valable ?

Oui. Créer un ensemble à partir de tous les éléments de nums et vérifier s’il est plus petit que le tableau donne la bonne réponse en temps O(n) . La version avec une boucle est souvent préférable, car elle renvoie un résultat dès qu’elle rencontre le premier doublon, tandis que la création de l’ensemble complet lit toujours toutes les valeurs.

FacileHachage

+10

Tu reçois un tableau d’entiers nums. Renvoie true si une valeur apparaît au moins deux fois, et false si toutes les valeurs sont différentes.

Fonction

containsDuplicate(nums: integer-array) → boolean

numsinteger-array: les entiers à vérifier
Renvoieboolean: vrai si une valeur apparaît au moins deux fois, faux sinon

Contraintes

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Exemples

Entrée: nums = [3, 1, 4, 1, 5]
Sortie: true
Explication: La valeur 1 apparaît à l’index 1 et de nouveau à l’index 3, donc la réponse est true.

Entrée: nums = [2, 7, 1, 8]
Sortie: false
Explication: 2, 7, 1 et 8 sont quatre valeurs différentes, donc rien ne se répète.

Entrée: nums = [-4, 4, 0]
Sortie: false
Explication: -4 et 4 ont la même valeur absolue, mais ce sont des nombres différents, et 0 apparaît une seule fois, donc la réponse est false.

+17 tests cachés à la soumission

Pour aller plus loin

Peux-tu t’arrêter dès que tu rencontres la première valeur répétée, au lieu de toujours parcourir tout le tableau ?

Indices

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

0 sur 3 ouverts

Solution

Un doublon est une valeur que tu as déjà rencontrée, et le travail consiste à répondre rapidement à la question « ai-je déjà rencontré cette valeur ? ». Comparer chaque paire permet d’y répondre, mais pour n = 10^4, cela représente n(n-1)/2, soit environ 5 × 10^7 comparaisons. Le tri place les valeurs égales côte à côte, et un ensemble de hachage répond à la question en O(1) en moyenne, ce qui permet un seul parcours.

Trier, puis comparer les voisins

Intuition

Dans un tableau trié, les valeurs égales se trouvent côte à côte. [3, 1, 4, 1, 5] devient [1, 1, 3, 4, 5] après le tri, et les deux 1s sont alors côte à côte. Après le tri, il suffit donc de comparer chaque valeur à celle qui la précède : n-1 comparaisons au lieu des n(n-1)/2 nécessaires pour essayer toutes les paires.

S’il n’y a pas deux voisins égaux, aucune valeur n’est égale à une autre, où qu’elle se trouve : toute valeur située entre deux occurrences de x dans l’ordre trié devrait être à la fois supérieure ou égale à x et inférieure ou égale à x ; ce serait donc une autre occurrence de x.

Le tri détermine la complexité, qui est de O(n log n) en temps. Trier nums sur place ne nécessite aucun tableau supplémentaire, mais réordonne l’entrée de l’appelant ; si cela n’est pas permis, trie une copie, ce qui nécessite un espace de O(n).

Algorithme

Triez nums par ordre croissant.
Parcourez i de 1 jusqu'au dernier indice.
Si nums[i] est égal à nums[i-1], renvoyez true.
Après la boucle, renvoyez false.

def containsDuplicate(nums):
    nums.sort()
    # After sorting, equal values sit next to each other.
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False

Un seul passage avec un ensemble de hachage

Intuition

Parcourez le tableau une seule fois et conservez chaque valeur déjà parcourue dans un ensemble de hachage. Avant d’ajouter une valeur, demandez à l’ensemble si elle s’y trouve déjà. Pour [3, 1, 4, 1, 5], l’ensemble contient successivement {3, 1, 4} et, lorsque le deuxième 1 arrive, l’ensemble le contient déjà : vous renvoyez donc true sans lire le 5.

L’ensemble contient toujours exactement les valeurs situées avant la position actuelle : une correspondance signifie que la valeur actuelle est déjà apparue, et si vous atteignez la fin sans correspondance, toutes les valeurs sont différentes.

La recherche et l’insertion dans un ensemble de hachage prennent en moyenne un temps de O(1), donc le parcours complet prend O(n). Le prix à payer est la mémoire : en l’absence de répétition, l’ensemble finit par contenir les n valeurs.

Algorithme

Créez un ensemble de hachage vide seen.
Pour chaque valeur de nums, si elle se trouve dans seen, renvoyez true.
Sinon, ajoutez-la à seen.
Après la boucle, renvoyez false.

def containsDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Pièges et cas limites

La logique est simple ; les bugs se trouvent donc dans les bornes des boucles et dans ce que vous comparez.

Comparer chaque paire en faisant commencer la boucle interne à j = i. Chaque valeur correspond alors à elle-même, et la réponse est toujours true.
Comparer les voisins sans trier d’abord. Dans [9, 1, 2, 3, 9], les deux 9 ne sont pas côte à côte.
Faire commencer la boucle sur les voisins à l’indice 0 et lire nums[-1]. Commencez à 1 : un tableau d’une seule valeur renvoie alors correctement false.
Considérer que les valeurs ayant la même valeur absolue sont égales, par exemple en calculant un hachage de abs(x). -4 et 4 sont des nombres différents.
Écrire un comparateur de tri en C qui renvoie x - y. Ici, la différence reste dans l’intervalle ±2 × 10^9, inférieur à la limite de int, 2^31-1 = 2147483647 ; elle tient donc par chance dans cette plage. Avec des valeurs proches des limites de int, il y a débordement et le tri donne un résultat incorrect. Renvoyez plutôt (x > y) - (x < y).

Questions fréquentes4

Quelle est la complexité temporelle de Contains Duplicate ?

La solution utilisant un ensemble de hachage s’exécute en temps O(n) en moyenne et utilise un espace supplémentaire O(n). Le tri préalable prend un temps O(n log n) et ne nécessite pas de tableau supplémentaire si tu peux réordonner l’entrée. Comparer chaque paire prend un temps O(n²).

Peux-tu résoudre Contains Duplicate sans espace supplémentaire ?

Oui, si tu as le droit de réordonner le tableau : trie-le sur place et compare chaque valeur avec sa voisine. Cela remplace l’ensemble en O(n) par un temps en O(n log n). Sans réordonner le tableau et sans mémoire supplémentaire, la seule option restante est de vérifier les paires en O(n²).

Pourquoi un ensemble de hachage rend-il la vérification rapide ?

Un ensemble de hachage stocke les valeurs à l’aide de leur hachage ; vérifier s’il contient une valeur prend donc un temps constant en moyenne, au lieu de parcourir les éléments. Chaque élément nécessite une recherche et une insertion, ce qui rend le parcours complet linéaire.

Comparer la taille de l’ensemble à la longueur du tableau est-il une solution valable ?

Oui. Créer un ensemble à partir de tous les éléments de nums et vérifier s’il est plus petit que le tableau donne la bonne réponse en temps O(n). La version avec une boucle est souvent préférable, car elle renvoie un résultat dès qu’elle rencontre le premier doublon, tandis que la création de l’ensemble complet lit toujours toutes les valeurs.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

true