比较算法

我有2个数组（A和B），其中包含有些差异的相似数据。我想返回仅在A中的对象数组和仅在B中的另一个对象数组。到目前为止，我一直在想：比较算法

一些优化蛮力（这是微不足道的）
排序的阵列和使用二进制搜索。

我的其他选择是什么？任何语言/解决方案都是公平游戏。

来源

2009-08-11 Joe Cannatti

您可以对两个数组进行排序，然后同时对两个数组进行线性扫描。这将是用于排序的O（nlogn）算法和用于扫描/建立新阵列的O（n）。

来源

2009-08-11 02:49:06

尝试使用集合。他们通常有一个差异（）方法（或类似的东西），返回到你想要的。就那么简单。一旦语言不可知，如何创建集合或将差异转换为数组就是使用一般方法完成的。

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++; 
    } 
}

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

来源

2009-08-11 02:49:38

正是我要说的。例如Python的sets模块，你可以使用差异（）或简单的“ - ”运算符。 http://docs.python.org/library/sets.html – MatrixFrog 2009-08-11 02:51:10

我认为他正在寻找隐藏的算法。这里有很多简单的单行（想想LINQ），但是他们真的没有教我们什么，我们不知道没有阅读文档，他们的效率是什么。 – JoshJordan 2009-08-11 02:51:11

我知道的两套算法是哈希集合和树集合。 Google或SO搜索这些条款。 – MatrixFrog 2009-08-11 02:53:30

我没有实现或算法超越什么的已经说过，但我想我会留在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

来源

2009-08-11 03:11:56

很多这将取决于你有什么类型的数据。你提到排序，所以我认为它的元素是可比的。随着套尺寸m和n，这将需要进行排序，这将占主导地位。（渐近地说，如果你进行二分搜索或者走这两个列表都没有关系，走这两个列表应该是O(m + n)。）当然，如果你正在使用更好的排序算法可用的数据，比如带有基数排序的整数，你应该可以降到O(m + n)。

使用集合（正如其他人所暗示的）隐含地建议使用散列，这肯定会使您的问题更容易。如果散列A中的所有元素（O(m)），并将散列集中的所有散列存储在内存中，则散列B（O(n)）并检测散列集中可能发生冲突的位置。这成为优化的问题：您必须评估经典的速度 - 内存折衷。散列集越大，碰撞检查的速度就越快。这将在O(m + n)中运行。

值得注意的是，你可以证明任何你要求的算法至少会在至少m + n时间内运行，因为需要查看所有的输入。

来源

2009-08-11 03:13:40

@David：在比较排序与散列表方法时，您还需要考虑1）散列函数计算的代价与比较成本（针对不等于的情况进行优化）以及2）散列函数是否给出一个很好的传播。 – 2009-08-11 03:40:49

@Stephen绝对！我不想考虑这些考虑因素，因为它们往往需要对我们没有的投入进行假设。 – 2009-08-13 00:43:03

我想将数组A的元素填充到散列表中，然后遍历数组B在哈希表中进行查找以有效地确定B中的哪些元素也在A.然后在遍历数组A的同时在散列表中对B的元素执行同样的操作。这将始终是O（N）。

来源

2009-08-11 03:15:49

哈希表往往会生成更快的算法，但通常会占用大部分内存。顺便说一句好的答案 – 2009-08-11 03:24:40

回答

相关问题