Самое быстрое сравнение массивов

Question

У меня есть два отсортированных массива (может быть ArrayLists, Коллекции или любой другой формат данных) уникальных значений. Какой самый быстрый способ сравнить их? Цель состоит в том, чтобы удалить все значения, присутствующие в обоих списках.

Начните с:

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

Конец:

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

Answer 1

Использовать измененную версию шага слияния в MergeSort

• получить итератор для каждого массива
• сравнить значения итераторов
• если равно, увеличивайте оба
• если не равно, поместите меньшее значение в массив уникальных значений и увеличивайте только этот итератор
• повторять до конца массива
• если они остались в другом массиве, они уникальны

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