判断两个数组是否具有相同成员的算法

比较两个数组以查看它们是否具有相同成员的最佳算法是什么？

假设没有重复项,成员可以按任何顺序排列,并且两者都没有排序.

compare(
    [a, b, c, d],
    [b, a, d, c]
) ==> true

compare(
    [a, b, e],
    [a, b, c]
) ==> false

compare(
    [a, b, c],
    [a, b]
) ==> false

Mark Bessey.. 18

明显的答案是:

对两个列表进行排序,然后检查每个元素以查看它们是否相同

将一个数组中的项添加到哈希表中,然后遍历另一个数组,检查每个项是否在哈希中

nickf的迭代搜索算法

你使用哪一个取决于你是否可以先对列表进行排序,以及是否有一个好的哈希算法.

1> Mark Bessey..：

---

明显的答案是:

对两个列表进行排序,然后检查每个元素以查看它们是否相同

将一个数组中的项添加到哈希表中,然后遍历另一个数组,检查每个项是否在哈希中

nickf的迭代搜索算法

你使用哪一个取决于你是否可以先对列表进行排序,以及是否有一个好的哈希算法.

---

从数学角度来看,集合不包含两次相同的值.

---

哈希表方法的问题是当列表可以具有重复值时它不起作用.是[1,2,2,3] == b [1,2,3,3]？两者的长度相同,b中的所有项都可以在a的哈希表中找到.您需要一个设置结构来计算项目并检查计数是否相等.

2> Andru Luvisi..：

---

您可以将一个加载到哈希表中,跟踪它有多少个元素.然后,循环遍历第二个,检查其每个元素是否都在哈希表中,并计算它有多少个元素.如果第二个数组中的每个元素都在哈希表中,并且两个长度匹配,则它们是相同的,否则它们不相同.这应该是O(N).

要在存在重复项的情况下使其工作,请跟踪每个元素的数量.在第一个数组上循环时递增,在第二个数组上循环时递减.在第二个数组的循环期间,如果您在哈希表中找不到某些内容,或者计数器已经为零,则它们是不相等的.还要比较总计数.

在存在重复的情况下工作的另一种方法是对两个数组进行排序并进行线性比较.这应该是O(N*log(N)).

3> 小智..：

---

假设你不想打扰原始数组和空间是一个考虑因素,另一个使用比排序两个数组更少空间的O(n.log(n))解决方案是:

如果数组大小不同,则返回FALSE

排序第一个数组--O(n.log(n))时间,所需的额外空间是一个数组的大小

对于第二个数组中的每个元素,使用二进制搜索检查它是否在第一个数组的排序副本中 - O(n.log(n))时间

如果您使用此方法,请使用库例程进行二进制搜索.二进制搜索出乎意料地容易出错.

[在审查建议字典/集合/散列查找的解决方案后添加:]

在实践中我会使用哈希.有几个人已经断言哈希的O(1)行为,导致他们得出一个基于哈希的解决方案是O(N).典型的插入/查找可能接近于O(1),并且一些散列方案保证最坏情况下的O(1)查找,但是在构造散列时最坏情况插入不是O(1).给定任何特定的散列数据结构,会有一些输入会产生病态行为.我怀疑存在散列数据结构,其中最坏情况为[插入N元素然后查找-N元素] O(N.log(N))时间和O(N)空间.