Contains Duplicate

Description

[EN]

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

[FR]

Étant donné un tableau d'entiers nums, il faut déterminer s'il contient au moins deux éléments identiques. Par exemple:

• nums = [1,2,3,4] : aucun doublon → résultat : false

• nums = [1,2,3,2] : contient un doublon (2) → résultat : true

Approche initiale : Double boucle imbriquée

Une première méthode intuitive consiste à comparer chaque élément du tableau avec tous les autres. C'est de cette manière que j'ai procédé. Voici ci-dessous le code écrit:

• Logique : La boucle externe parcourt chaque élément nums[i]. La boucle interne compare cet élément à tous ceux qui viennent après (nums[j]).

• Complexité temporelle : Avec deux boucles imbriquées, chaque paire d'éléments est comparée une fois. Cela donne une complexité quadratique O(n²), ce qui peut devenir lent si le tableau est grand.

• Complexité spatiale : Aucun espace supplémentaire n'est utilisé en dehors de quelques variables. La complexité spatiale est donc O(1).

Approche optimisée: Utilisation d'un HashSet

La première méthode est assez intuitive mais devient inefficace pour les tableaux de grande taille en raison de sa complexité.

1. Initialisation :

   • Un HashSet appelé alreadyMetNumbers est créé pour suivre les nombres déjà rencontrés dans le tableau.

2. Parcours du tableau :

   • On parcourt chaque élément nums[i] du tableau.

3. Ajout au HashSet :

   • La méthode add du HashSet tente d'insérer l'élément nums[i] dans l'ensemble.

   • Si l'élément était déjà présent dans le HashSet, add retourne false, indiquant qu'un doublon a été trouvé.

   • Si un doublon est détecté, on retourne immédiatement true.

4. Fin du parcours :

   • Si aucun doublon n'est trouvé après avoir parcouru tout le tableau, on retourne false.

• Complexité temporelle :

  • Le tableau est parcouru une fois (O(n)).

  • Chaque ajout dans le HashSet est O(1) en moyenne.

  • Donc, la complexité globale est O(n).

• Complexité spatiale :

  • Le HashSet stocke jusqu'à n éléments uniques (dans le pire cas où tous les éléments sont distincts).

  • La complexité spatiale est donc O(n).