首頁猿問請教，比較兩個集合是否相等，而不論...

請教，比較兩個集合是否相等，而不論它們中項的順序如何

SQL Server

不負相思意 2019-10-20 16:12:17

比較兩個集合是否相等，而不論它們中項的順序如何我想比較兩個集合(在C#中)，但我不確定有效實現(xiàn)這一點的最佳方法。我讀過另一篇關于數(shù)列相等但這不是我要找的。在我的例子中，如果兩個集合都包含相同的項(不管順序如何)，那么兩個集合是相等的。例子：collection1 = {1, 2, 3, 4};collection2 = {2, 4, 1, 3};collection1 == collection2; // true我通常做的是循環(huán)遍歷一個集合的每個項，看看它是否存在于另一個集合中，然后循環(huán)遍歷另一個集合的每個項，并查看它是否存在于第一個集合中。(我首先比較長度)。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}這和我的實施是一樣的。我應該只計算找到每一項的次數(shù)并確保兩個集合中的計數(shù)相等嗎？這些例子都是在某種C#中(讓我們稱之為偽C#)，但是用您想要的語言給出答案并不重要。注：為了簡單起見，我在示例中使用了整數(shù)，但我也希望能夠使用引用類型的對象(它們不能正確地作為鍵運行，因為只比較了對象的引用，而不是內容)。

查看完整描述

3 回答

冉冉說

TA貢獻1877條經(jīng)驗獲得超1個贊

一個簡單且相當有效的解決方案是對兩個集合進行排序，然后比較它們是否相等：

bool equal = collection1.OrderBy(i => i).SequenceEqual(
                 collection2.OrderBy(i => i));

這個算法是O(N*logn)，而上面的解是O(N^2)。

如果集合具有某些屬性，則可以實現(xiàn)更快的解決方案。例如，如果兩個集合都是散列集，則它們不能包含重復項。此外，檢查哈希集是否包含某些元素非?？焖佟Ｔ谶@種情況下，類似于您的算法可能是最快的。

反對回復 2019-10-21

拉風的咖菲貓

TA貢獻1995條經(jīng)驗獲得超2個贊

創(chuàng)建一個字典“dict”，然后對第一個集合中的每個成員執(zhí)行dict[Members]+；

然后，以同樣的方式遍歷第二個集合，但是對于每個成員都是這樣做的[成員]-。

最后，循環(huán)遍歷字典中的所有成員：

    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;

    }

編輯：據(jù)我所知，這是與最有效的算法相同的順序。該算法是O(N)，假設字典使用O(1)查找。

反對回復 2019-10-21