Оптимизированный алгоритм синхронизации двух массивов

Question

Я ищу эффективный алгоритм для синхронизации двух массивов. Допустим, a1 и a2 - это два массива, заданных в качестве входных данных.

a1 - C, C ++, Java, C #, Perl

a2 - C ++, Python, Java, Cw, Haskel

Выход 2 массива:

Выход A1: C, C ++, Java

Выход A2: Cw, Haskell, Python

Выход A1:

1) элементы, общие для обоих массивов 2) предметы только в А1, а не в А2

Выход A2:

пунктов только в a2

Заранее спасибо.

Raj

Answer 1

1. Сортировка обоих массивов с эффективным алгоритмом сортировки, сложность O (n.log (n))
2. Создание выходных массивов изначально пустыми
3. Сравнить первый элемент a1 изотсортированный A1 по первому элементу a2 из отсортированного A2
   • Равные средние значения находятся в обоих массивах, поместите a1 в OutputA1
   • a1
   • , иначе a2

Делайте это, пока не обработаете все элементы в отсортированных массивах, сложность O (n).