217. Contains duplicate

Étant donné un tableau d'entiers nums, retourner vrai si une valeur apparaît au moins deux fois dans le tableau, et retourner faux si chaque élément est distinct.

LEETCODEARRAYS AND HASHING

Cheikhoul Khadim SECK

8/31/20242 min read

Description

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.

Étant donné un tableau d'entiers nums, retourner true si une valeur apparaît au moins deux fois dans le tableau, et retourner false si chaque élément est distinct.

Approche

On peut voir que c’est un problème de nombre d’occurrence, on peut donc utiliser une map non ordonnée ou hash table pour calculer les fréquences des éléments de l’array comme dans le problème de l’anagramme

Réflexions clés

  • La solution du Hash table fonctionne très bien mais n’est pas excellente ni en complexité mémoire ni en temps. En partant sur une solution qui débute par ordonner la liste, on obtient de bien meilleurs résultats sur notre utilisation de la mémoire. Par contre en terme de performances en runtime, on régresse. On passe du percentile 11 au 8. Et en local je passe de 33 à 42 ms pour passer 3 tests. On observe donc encore une fois le trade-off entre les deux types de complexité.

  • Ma méconnaissance des structures de données m’ont empêché de penser à utiliser un hash set pour résoudre le problème. Parmi les solutions sur la plateforme on a donc :

  • Cette utilisation des Set est aussi créative :

Ce code mets 36 ms à passer les 3 tests en local. C’est pas nécessairement meilleure que ce que j’avais au début.

Erreurs commises à éviter

  • Attention à bien respecter la consigne et rendre True si l’array contient des nombres dupliqués et False sinon.

Rectifications

  • Changer

en

Et on rentre dans le top 1% en terme de Complexité mémoire.

En savoir plus sur la série Arrays and Hashing

Cet article touche à sa fin, mais notre exploration des Arrays et Hashing ne fait que commencer. Ne manquez pas nos autres articles de la série pour approfondir vos connaissances, surtout si vous débutez ! Apprenez de mes expériences et progressez avec nous.