优化算法同步两个数组

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)仅在A1中而不在A2中的项目

输出A2:

物品只在a2

提前致谢.

拉吉

Answer 1

1. 使用有效的排序算法对两个数组进行排序,复杂度为O(n.log(n))
2. 最初构建输出数组为空
3. 将排序的A1的第一个元素a1与排序的A2的第一个元素a2进行比较
   • 两个数组都是等于平均值​​,将a1放入OutputA1
   • a1 <a2表示a1仅在A1中,a1现在是已排序A1中的下一个元素,将a1放入OutputA1
   • 否则a2 <a1表示a2仅在A2中,a2现在是在排序A2中的下一个元素,将a2放入OutputA2

这样做直到您处理排序数组中的所有元素,O(n)的复杂性.