请教，比较两个集合是否相等，而不论它们中项的顺序如何

Question

比较两个集合是否相等，而不论它们中项的顺序如何

我想比较两个集合(在C#中)，但我不确定有效实现这一点的最佳方法。

我读过另一篇关于数列相等但这不是我要找的。

在我的例子中，如果两个集合都包含相同的项(不管顺序如何)，那么两个集合是相等的。

例子：

collection1 = {1, 2, 3, 4};collection2 = {2, 4, 1, 3};collection1 == collection2; // true

我通常做的是循环遍历一个集合的每个项，看看它是否存在于另一个集合中，然后循环遍历另一个集合的每个项，并查看它是否存在于第一个集合中。(我首先比较长度)。

if (collection1.Count != collection2.Count)
    return false; // the collections are not equalforeach (Item item in collection1){
    if (!collection2.Contains(item))
        return false; // the collections are not equal}foreach (Item item in collection2){
    if (!collection1.Contains(item))
        return false; // the collections are not equal}return true; // the collections are equal

然而，这并不完全正确，而且它可能不是比较两个集合是否相等的最有效的方法。

我能想到的一个例子是，这是错误的：

collection1 = {1, 2, 3, 3, 4}collection2 = {1, 2, 2, 3, 4}

这和我的实施是一样的。我应该只计算找到每一项的次数并确保两个集合中的计数相等吗？

---

这些例子都是在某种C#中(让我们称之为伪C#)，但是用您想要的语言给出答案并不重要。

注：为了简单起见，我在示例中使用了整数，但我也希望能够使用引用类型的对象(它们不能正确地作为键运行，因为只比较了对象的引用，而不是内容)。

Answer 1

一个简单且相当有效的解决方案是对两个集合进行排序，然后比较它们是否相等：bool equal = collection1.OrderBy(i => i).SequenceEqual(                  collection2.OrderBy(i => i));这个算法是O(N*logn)，而上面的解是O(N^2)。如果集合具有某些属性，则可以实现更快的解决方案。例如，如果两个集合都是散列集，则它们不能包含重复项。此外，检查哈希集是否包含某些元素非常快速。在这种情况下，类似于您的算法可能是最快的。

Answer 2

创建一个字典“dict”，然后对第一个集合中的每个成员执行dict[Members]+；然后，以同样的方式遍历第二个集合，但是对于每个成员都是这样做的[成员]-。最后，循环遍历字典中的所有成员：&nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;bool&nbsp;SetEqual&nbsp;(List<int>&nbsp;left,&nbsp;List<int>&nbsp;right)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(left.Count&nbsp;!=&nbsp;right.Count) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Dictionary<int,&nbsp;int>&nbsp;dict&nbsp;=&nbsp;new&nbsp;Dictionary<int,&nbsp;int>(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;foreach&nbsp;(int&nbsp;member&nbsp;in&nbsp;left)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(dict.ContainsKey(member)&nbsp;==&nbsp;false) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dict[member]&nbsp;=&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dict[member]++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;foreach&nbsp;(int&nbsp;member&nbsp;in&nbsp;right)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(dict.ContainsKey(member)&nbsp;==&nbsp;false) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dict[member]--; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;foreach&nbsp;(KeyValuePair<int,&nbsp;int>&nbsp;kvp&nbsp;in&nbsp;dict)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(kvp.Value&nbsp;!=&nbsp;0) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;true; &nbsp;&nbsp;&nbsp;&nbsp;}编辑：据我所知，这是与最有效的算法相同的顺序。该算法是O(N)，假设字典使用O(1)查找。