时间戳

首页 > 解决方案 > C# 高效的 ContainsAll 重复项？

c# - C# 高效的 ContainsAll 重复项？

问题描述

类似于现有的“ContainsAll”方法，但特别是我想检查子列表中的任何重复项是否也存在于主列表中。例如。我有一些清单：

List<int> a = new List<int> { 1, 2, 1, 3 };
List<int> b = new List<int> { 1, 1, 2 };
List<int> c = new List<int> { 2, 2, 3 };

我想要的是bool ContainsAll(List<T> l1, List<T> l2)这样的函数ContainsAll(a, b) == true（因为重复的 1 对两个列表都是通用的）但是ContainsAll(a, c) == false（因为列表 a 没有多个 2）。

我当然可以通过主列表手动搜索，在我找到它们时删除它们。但是，这需要复制列表（因为我不想修改它），如果存在的话，我希望有一种更清洁/更快的方法。

ETA：我需要检查在较大列表中找到的每个元素的数量是否至少与较小列表中的一样多。不仅两个列表中都有多个，而且较小列表中的每个元素都可以与较大列表中的唯一元素配对。

我没有特定的性能要求。我真的只是想知道是否有比手动检查更“正确”的方法。您可能会争辩说，“正确”可能意味着更快、更具可读性，或者通过使用内置函数更容易编写。也许没有更好的方法。我要补充一点，我的用例可能涉及根据几个较小的列表检查较大的列表，因此一次性转换较大的列表（例如到字典）当然是一个考虑因素。

标签： c#.net

解决方案

您可以计算两个列表的每个元素，然后检查 in 中所有元素的计数l2是否小于或等于 in 中的相应计数l1。

using System.Collections.Generic;

static Dictionary<T, int> Count<T>(List<T> l)
{
    Dictionary<T, int> c = new Dictionary<T, int>();
    foreach (var o in l)
    {
        if (!c.ContainsKey(o))
            c[o] = 1;
        else
            c[o]++;
    }
    return c;
}

static bool ContainsAll<T>(List<T> l1, List<T> l2)
{
    Dictionary<T, int> c1 = Count(l1);
    Dictionary<T, int> c2 = Count(l2);
    foreach (var kvp2 in c2)
    {
        // If c1 doesn't contain the current value
        // or its count is < the current value's count in l2
        // return false
        if (!c1.ContainsKey(kvp2.Key) || c1[kvp2.Key] < kvp2.Value)
            return false;
    }
    // All checks were successful, return true
    return true;
}

在线尝试

当然，这种方法涉及构建字典，因此您会牺牲内存来提高速度，但它会比检查使用更快，List.Contains()因为在列表中查找是 O(n)

推荐阅读