Comment puis-je vérifier s'il y a des doublons de certains éléments dans une liste avec theta (n) temps?vérifier les doublons dans une liste
Cela signifie essentiellement que vous ne pouvez pas vérifier la liste entière pour chaque élément.
Effectuez une itération sur les éléments et placez-les dans une carte de hachage (vérification d'une collision). Comme l'insertion dans la table de hachage est O (1) vous devriez vous retrouver avec O (n) (itérer sur la liste) + O (1) (insérer et vérifier la carte de hachage pour la collision, le poussin est généralement une opération de la plupart des implémentations), et O (n) + O (1) -> O (n).
Tri par comptage? –
Pourriez-vous préciser si vous voulez: a) se débarrasser des doublons b) retourner les doublons c) savoir * si * il y a un ou plusieurs doublons? –