J'ai une ArrayList et je veux supprimer les chaînes répétées. Comment puis-je faire cela?
Voir aussi LinkedHashSet, si vous souhaitez conserver l'ordre.
Réponses
Trop de publicités?Si vous ne voulez pas de doublons dans une Collection, vous devriez vous demander pourquoi vous utilisez une Collection qui permet les doublons. La manière la plus simple de supprimer les éléments répétés est d'ajouter le contenu à un Set (qui ne permettra pas les doublons) puis d'ajouter à nouveau le Set à l'ArrayList:
Set set = new HashSet<>(votreListe);
votreListe.clear();
votreListe.addAll(set);Bien sûr, cela détruit l'ordre des éléments dans l'ArrayList.
Mais cela créera juste l'ensemble sans doublons, je veux savoir quel numéro était en double en O(n) temps
Chetan, trouver les éléments en O(n) est possible si l'ensemble des valeurs possibles est petit (pensez à Byte ou Short); un BitSet ou similaire peut ensuite être utilisé pour stocker et rechercher les valeurs déjà rencontrées en O(1) temps. Mais encore une fois - avec un si petit ensemble de valeurs, le faire en O(n log n) pourrait de toute façon ne pas poser de problème puisque n est faible. (Ce commentaire ne s'applique pas à l'auteur original, qui doit le faire avec String.)
abahgat
Points
6479
Bien que la conversion de l'ArrayList en un HashSet supprime efficacement les doublons, si vous avez besoin de préserver l'ordre d'insertion, je vous suggère plutôt d'utiliser cette variante
// list est une Liste de Strings
Set s = new LinkedHashSet<>(list);Ensuite, si vous avez besoin de récupérer une référence de type List, vous pouvez à nouveau utiliser le constructeur de conversion.
LinkedHashSet fait-il des garanties quant à la conservation de plusieurs doublons de la liste ? Par exemple, si les positions 1, 3 et 5 sont des doublons dans la liste d'origine, peut-on supposer que ce processus supprimera 3 et 5 ? Ou peut-être supprimer 1 et 3 ? Merci.
@Matt: oui, cela le garantit. Les docs disent : "Cette liste chaînée définit l'ordre d'itération, qui est l'ordre dans lequel les éléments ont été insérés dans l'ensemble (ordre d'insertion). Notez que l'ordre d'insertion n'est pas affecté si un élément est réinséré dans l'ensemble."
Très intéressant. J'ai une situation différente ici. Je n'essaie pas de trier une chaîne de caractères mais un autre objet appelé AwardYearSource. Cette classe a un attribut int appelé année. Je veux donc supprimer les doublons en fonction de l'année. c'est-à-dire, s'il y a l'année 2010 mentionnée plus d'une fois, je veux supprimer cet objet AwardYearSource. Comment puis-je faire cela ?
Vitalii Fedorenko
Points
17469
En Java 8 :
List deduped = list.stream().distinct().collect(Collectors.toList());Veuillez noter que le contrat hashCode-equals pour les membres de la liste doivent être respectés pour que le filtrage fonctionne correctement.
@StackFlowed Si vous n'avez pas besoin de conserver l'ordre de la liste, vous pouvez utiliser addAll pour new TreeSet(String.CASE_INSENSITIVE_ORDER). Le premier élément ajouté restera dans l'ensemble. Ainsi, si votre liste contient "Chien" et "chien" (dans cet ordre), le TreeSet contiendra "Chien". Si l'ordre doit être préservé, alors avant la ligne dans la réponse, ajoutez list.replaceAll(String::toUpperCase);.
Bno
Points
5688
Si vous ne voulez pas de doublons, utilisez un Set au lieu d'une List. Pour convertir une List en un Set, vous pouvez utiliser le code suivant :
// list est une List de Strings
Set s = new HashSet(list);Si vraiment nécessaire, vous pouvez utiliser la même construction pour convertir un Set en List.
De même, en bas du fil de discussion, j'ai donné une réponse où j'utilise Set pour l'objet personnalisé. Dans le cas où quelqu'un a un objet personnalisé comme "Contact" ou "Étudiant", il peut utiliser cette réponse qui fonctionne bien pour moi.
Le problème survient lorsque vous devez spécifiquement accéder à un élément. Par exemple, lors de la liaison d'un objet à une vue d'élément de liste dans Android, vous obtenez son index. Ainsi, Set ne peut pas être utilisé ici.
stbn
Points
151
Voici une façon qui n'affecte pas l'ordre de votre liste:
ArrayList l1 = new ArrayList();
ArrayList l2 = new ArrayList();
Iterator iterator = l1.iterator();
while (iterator.hasNext()) {
YourClass o = (YourClass) iterator.next();
if(!l2.contains(o)) l2.add(o);
}l1 est la liste originale et l2 est la liste sans éléments répétés (Assurez-vous que YourClass a la méthode equals selon ce que vous voulez représenter par égalité)
Cette réponse manque de deux choses : 1) Il n'utilise pas les génériques, mais des types bruts (ArrayList devrait être utilisé à la place de ArrayList) 2) La création explicite de l'itérateur peut être évitée en utilisant un for (T current : l1) { ... }. Même si vous vouliez utiliser un Iterator explicitement, iterador est mal orthographié.
Et cette implémentation fonctionne en temps quadratique, par rapport à l'implémentation de l'ensemble de hachage lié qui s'exécute en temps linéaire. (c'est-à-dire que cela prend 10 fois plus de temps sur une liste avec 10 éléments, 10 000 fois plus de temps sur une liste avec 10 000 éléments. Implémentation JDK 6 pour ArrayList.contains, l'implémentation JDK8 est la même.)
