J'ai 2 listes, une liste l1 contient n1 éléments et une autre liste l2 contient n2 éléments.Les deux listes ne sont pas la même longueur et contiennent des éléments en double.Je veux créer une autre liste qui a des éléments uniques à la fois l1 et l2.Comment puis-je le faire efficacement et quelle serait la performance de cette solution?Structure des données: Unicité dans les listes
P.S: je veux une solution qui n'utilise pas d'autres structures de données.
Créer un nouvel ensemble et ajouter des éléments à partir des deux listes l1 et l2. L'ensemble final sera celui qui ne contient aucun doublon. Mais assurez-vous que vous avez implémenté equals() et hashCode() correctement.
Ci-dessous est mon échantillon (pas parfait) pour faire la même chose. Affichage ici pour valider ma logique ;-) ou pour voir s'il y a de meilleures façons d'optimiser cette
Lit unique=...
if(l1.size==l2.size())
{
//o(n)
copyToUnique(l1, l2, unique)
}
else if(l1.size>l2.size())
{
//o(n) + num of extra elements
copyToUnique(l1, l2, unique)
unique.addAll(l1.subList(l2.size(),l1.size());
}
else if(l1.size<l2.size())
{
//o(n) + num of extra elements
copyToUnique(l2, l1, unique)
unique.addAll(l2.subList(l1.size(),l2.size());
}
public void copyToUnique(List l1, List l2, List unique)
{
for(Object element:l1)
{
if(!l2.contains(element))
{
unique.add(element);
}
}
unique.addAll(l2);
}
+1 me battre. – casablanca
Que faire si je ne suis pas autorisé à utiliser une autre structure de données? – Jony
OP veut une liste, pas un ensemble. – dogbane
Si vous ne pouvez pas utiliser un ensemble, je pense que la meilleure solution est de faire une fusion tri sans doublon. Cette question peut aider: How do I use merge sort to delete duplicates?
Si vous devez utiliser uniquement des listes, et vous avez la possibilité de dupliquer à la fois dans chaque liste ET à travers les listes, alors vous devez créer une nouvelle liste, l3 (pour maintenir l'union de l1 et l2 éléments) et parcourez chaque liste, en insérant un élément de chaque élément e si un appel à l3.contains (e) renvoie false.
Comme d'autres l'ont mentionné, l'utilisation d'un ensemble est certainement le moyen le plus simple de supprimer des éléments en double d'une liste, et une liste peut être créée à partir de l'ensemble pour retourner à l'appelant.
La performance est linéaire et basée sur le nombre d'éléments dans l1 + l2.
performance de ce n'est pas linéaire, c'est O (n^2), ou quelque chose comme ça. Vous devez considérer la vérification si la troisième liste contient déjà l'élément. – nojo
Cela ne fait pas O (n^2). Cela dépend vraiment de l'implémentation de List utilisée, mais le cas le plus défavorable qui contient l'implémentation du SDK sera linéaire (ArrayList) et l'insertion sera linéaire. Donc, même si ce n'est pas un O (n) droit, il y a un multiplicateur et une croissance linéaire, PAS un exposant et une croissance quadratique. – Jeff
Cela dépend si l3 est trié ou non. Si non trié, et en supposant le pire cas de non-doublons, l3.contains() sera exécuté sur une liste de taille croissante, exécutant de 0 comparaisons au début à N = (l1 + l2-1) comparaisons à la fin: somme (0 .. N) = N * (N-1)/2. – Lars
Une solution O (nlogn) consisterait à trier chaque liste, puis à parcourir les deux listes ensemble pour trouver des doublons. Vous pouvez incrémenter la position d'une liste ou de l'autre liste (ou les deux) en fonction de la liste ayant la "plus petite" valeur de l'élément en cours (ou si elles sont identiques). Il y a un peu de surcharge, donc certains algorithmes O (n^2) pourraient être plus rapides en fonction de la taille/distribution des données.
Est-ce ce devoir? Cela ressemble à ça. –
Est-ce que chaque liste contient éventuellement des éléments en double ou voulez-vous dire seulement qu'il y a possibilité de duplication entre les listes? – Jeff
@Cameron: c'est une question d'entrevue. – Jony