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
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.
© 2023 CKS. Tous droits réservés..
Transformer les données et créer des expériences numériques.
Suivez nous
Explorer
Coordonnées
Courriel : contact@cheikhoulkhadimseck.com
Tél : +33752318179
Mentions
