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

請教，比較兩個(gè)集合是否相等，而不論它們中項(xiàng)的順序如何

SQL Server

不負(fù)相思意 2019-10-20 16:12:17

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

查看完整描述

3 回答

冉冉說

TA貢獻(xiàn)1877條經(jīng)驗(yàn) 獲得超1個(gè)贊

一個(gè)簡單且相當(dāng)有效的解決方案是對兩個(gè)集合進(jìn)行排序，然后比較它們是否相等：

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

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

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

反對回復(fù) 2019-10-21

拉風(fēng)的咖菲貓

TA貢獻(xiàn)1995條經(jīng)驗(yàn) 獲得超2個(gè)贊

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

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

最后，循環(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)，假設(shè)字典使用O(1)查找。

反對回復(fù) 2019-10-21