打印两个数组差异的最有效方法？
最近，我的一位同事问我如何测试两个数组的等价性。他有两个Address来源，并希望断言这两个来源包含完全相同的元素，尽管顺序并不重要。既可以使用Array，也可以使用Java语言中的List或IList，但是因为可以有两个相等的Address对象，所以不能使用Set这样的对象。
在大多数编程语言中，List已经有一个equals方法进行比较(假设在执行比较之前对集合进行了排序)，但是没有关于实际差异的信息；只知道有一些差异，或者没有差异。
输出应该通知在一个集合中但不在另一个集合中的元素，反之亦然。
一种显而易见的方法是遍历其中一个集合(如果其中一个是)，然后在另一个集合上调用contains(element)，然后以另一种方式执行。假设contains的O(n)的复杂性，如果我是正确的，这将导致O(2n²)。
有没有更有效的方法来获取这样的信息："A1和A2不在List1中，A3和A4不在List2中“？有没有比列表更适合做这项工作的数据结构？在使用自定义的二进制搜索包含之前对集合进行排序是否值得？
回答 2
Stack Overflow用户
发布于 2015-06-12 17:16:05
首先想到的是使用集合差值
在伪python中
addr1 = set(originalAddr1)
addr2 = set(originalAddr2)
in1notin2 = addr1 - addr2
in2notin1 = addr2 - addr1
allDifferences = in1notin2 + in2notin1从here中，您可以看到set difference为O(len(set))，union为O(len(set1) + len(set2))，使用这个特定于python的set实现为您提供线性时间解决方案，而不是您建议的二次型。
我相信其他流行的语言倾向于以几乎相同的方式实现这些类型的数据结构，但不能真正确定这一点。
Stack Overflow用户
发布于 2015-06-12 17:16:40
是否值得对集合进行排序...？
将朴素的方法O(n²)与在O(n logn)中对两个列表进行排序，然后在O(n)中进行比较，或者在O(n logn)中对一个列表进行排序并在O(n)中迭代另一个列表进行比较
https://stackoverflow.com/questions/30799294
复制相似问题
腾讯云开发者
