9

我有两个列表 A 和 B（列表）。如何以最便宜的方式确定它们是否相等？我可以写类似'（A减B）联合（B减A）=空集'或将它们连接在一起并计算元素数量，但它相当昂贵。有解决方法吗？

4

5 回答 5

18

如果列表项的顺序相关：

bool areEqual = a.SequenceEqual(b);

如果将列表视为无序集：

// assumes that the list items are ints
bool areEqual = new HashSet<int>(a).SetEquals(b);

（如果您需要该功能，SequenceEqual方法和HashSet<T>构造函数都具有带参数的重载。）IEqualityComparer<T>

于 2009-06-03T15:14:46.443 回答
7

嗯，这取决于你如何解释你的列表。

如果您将它们视为元组（因此列表中元素的顺序很重要），那么您可以使用以下代码：

    public bool AreEqual<T>(IList<T> A, IList<T> B)
    {
        if (A.Count != B.Count)
            return false;
        for (int i = 0; i < A.Count; i++)
            if (!A[i].Equals(B[i])) 
                return false;
    }

如果您将列表视为集合（因此元素的顺序无关紧要），那么......我猜您使用的是错误的数据结构：

    public bool AreEqual<T>(IList<T> A, IList<T> B)
    {
        HashSet<T> setA = new HashSet<T>(A);
        return setA.SetEquals(B);
    }
于 2009-06-03T14:51:04.493 回答
1

这取决于“列表相等”的含义。如果您的意思是它们包含相同的对象，丹尼尔建议的解决方案很好，只需 Union() 两个列表并计算项目。

如果“相等”是指它们以相同的顺序具有相同的项目，则最好比较两个列表的计数，然后如果它们具有相同的计数，只需使用普通迭代for loop来比较两者中的每个元素在同一索引处列出。不那么漂亮，但你几乎不能更快。

于 2009-06-03T14:47:43.783 回答
1

实际上，这里没有捷径，除非列表已排序，在这种情况下，您可以逐个比较元素。显然我认为顺序无关紧要，否则很明显你也可以一一比较它们。

否则，我建议您可以为大型项目列表获得的最有效算法可能是这样的，使用哈希表来跟踪您所看到的（警告：尚未测试，但它应该清楚我的意思。）

public static bool IsEqual<T>(this List<T> x1, List<T> x2)
{
    if(x1.Count != x2.Count) return false;

    var x1Elements = new Dictionary<T, int>();

    foreach(var item in x1)
    {
        int n; x1Elements.TryGetValue(item, out n);
        x1Elements[item] = n+1;
    }

    foreach(var item in x2)
    {
        int n; x1Elements.TryGetValue(item, out n);
        if(n <= 0) return false; // this element was in x2 but not x1
        else x1Elements[item] = n-1;
    }

    // make sure x1 didn't have any elements
    // that weren't in x2

    return x1Elements.Values.All(x => x == 0);
}
于 2009-06-03T14:49:30.333 回答
-1

第一次拍摄 - 如果它们包含相同的项目，则两个列表的并集应该与两个列表中的任何一个具有相同数量的项目。

listA.Union(listB).Count() == listA.Count()

注意：如果一个列表为空，则失败。

但这可能仍然是一项O(n²)手术。

另一种解决方案 - 列表必须具有相同的长度，并且列表 A 减去列表 B 不得包含任何元素。

(listA.Count() == listB.Count()) && !listA.Except(listB).Any()
于 2009-06-03T14:42:47.897 回答