比较算法

您可以对两个阵列进行排序,然后同时对两个阵列进行线性扫描。这将是用于排序的O(nlogn)算法,以及用于扫描/构建新阵列的O(n)算法。

我将数组A的元素填充到一个哈希表中,然后遍历数组B在哈希表中进行查找,以有效地确定B中的哪些元素也在A中。然后在遍历数组A的同时对哈希表中的B元素执行相同的操作。这将是O(N)。

这在很大程度上取决于您拥有的数据类型。你提到排序,所以我认为元素是可比较的。有几套尺寸 m 和 n ,这将需要 O(m lg m + n lg n) 排序,这将占主导地位。(渐进地说,不管是进行二进制搜索还是遍历两个列表,遍历两个列表都应该是可行的 O( m + n) O(m+n) .

使用集合(正如其他人所建议的)隐含地建议使用哈希,这肯定会使问题变得更容易。如果将( O(m) )并将所有散列存储在内存中的散列集中,然后散列B( O(n) )并检测哈希集中可能发生冲突的位置。这就成为了一个优化问题:您必须评估一个经典的速度内存权衡。哈希集越大,冲突检查就越快。这将运行在 O( m + n ) .

值得注意的是,您可以证明,任何满足您要求的算法都至少可以在 m + n 时间,因为需要查看所有输入。

除了已经说过的,我没有实现或算法,但我想我会把这个解决方案留在c#/linq中,留给任何可能发现这个问题并想这样做的人:

    var a = new int[] { 1, 2, 3, 6, 7, 8, 9, 10 };
    var b = new int[] { 1, 2, 3, 4, 5, 6, 7 };

    int[] addedToA = a.Except(b);
    int[] missingFromA = b.Except(a);

    foreach (var i in addedToA)
    {
        Console.Write("{0} ", i);
    }
    Console.WriteLine();
    foreach (var i in missingFromA)
    {
        Console.Write("{0} ", i);
    }

这张照片是:

8 9 10
4 5

Set A = createSetA();
Set B = createSetB();

Array onlyAElements = transformToArray(A.difference(B));
Array onlyBElements = transformToArray(B.difference(A));

或者,您可以对两个数组进行排序,同时获得两个不同的数组。差不多

int aIndex = 0;
int bIndex = 0;

Array aOnly = new Array();
Array bOnly = new Array();

while (aIndex != a.length || bIndex != b.length)
{
   if (A[aIndex] == B[bIndex]
   {
       aIndex++;
       bIndex++;
   }
   else if (A[aIndex] > B[bIndex])
   {
       aOnly.add(A[aIndex]);
       aIndex++;
   }
   else 
   {
       bOnly.add(B[bIndex]);
       bIndex++;
   }
} 

你应该记住在出界时有一些错误。但是代码只是为了得到主要的想法。