Comparaison de tableaux la plus rapide

Question

J'ai deux tableaux triés (peuvent être ArrayLists, Collections ou tout autre format de données) de valeurs uniques. Quel est le moyen le plus rapide de les comparer? L'objectif est de supprimer toutes les valeurs présentes dans les deux listes.

Commencez par:

int [] a = {1, 2, 3, 4, 5}; 
int [] b = {1, 2, 3, 6, 7}; 

End avec:

a = {4, 5} 
b = {6, 7} 

Answer 1

Utilisez une version modifiée de l'étape de fusion dans MergeSort

• obtenir un itérateur pour chaque tableau
• comparer valeurs des itérateurs
• en cas d'égalité, incrémenter les deux
• sinon égale, mettez moindre valeur dans un tableau de valeurs uniques et incrémenter seulement que iterator
• répétition jusqu'à la fin d'un tableau est remplie
• le cas échéant à gauche dans d'autres tableaux, les sont uniques

Answer 2

List list = Arrays.asList(a); 

list.retainAll(b); //now list has {1, 2, 3} 

List result = Arrays.asList(a).removeAll(list); //it now has 4, 5. For b do the same