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

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]+；

然后，以同样的方式遍历第二个集合，但是对于每个成员都是这样做的[成员]-。

最后，循环遍历字典中的所有成员：

    private bool SetEqual (List<int> left, List<int> right) {

        if (left.Count != right.Count)
            return false;

        Dictionary<int, int> dict = new Dictionary<int, int>();

        foreach (int member in left) {
            if (dict.ContainsKey(member) == false)
                dict[member] = 1;
            else
                dict[member]++;
        }

        foreach (int member in right) {
            if (dict.ContainsKey(member) == false)
                return false;
            else
                dict[member]--;
        }

        foreach (KeyValuePair<int, int> kvp in dict) {
            if (kvp.Value != 0)
                return false;
        }

        return true;

    }

编辑：据我所知，这是与最有效的算法相同的顺序。该算法是O(N)，假设字典使用O(1)查找。