C# 如何实现支持重复元素计数校验的高效ContainsAll方法？

实现思路 #

核心逻辑是分别统计主列表和待校验子列表的元素出现频次，再校验子列表所有元素的出现次数都不超过主列表对应元素的出现次数，不需要复制主列表做修改，效率和可读性都更高。

单次调用版本（简洁实现） #

直接用内置LINQ方法完成统计和比对，代码量少易维护：

using System.Collections.Generic;
using System.Linq;

public static class ListExtension
{
    public static bool ContainsAll<T>(this List<T> source, List<T> toCheck, IEqualityComparer<T> comparer = null)
    {
        comparer ??= EqualityComparer<T>.Default;
        // 统计主列表各元素的出现次数
        var sourceFreq = source.GroupBy(x => x, comparer)
                               .ToDictionary(g => g.Key, g => g.Count(), comparer);
        // 遍历子列表的频次统计结果做校验
        foreach (var checkGroup in toCheck.GroupBy(x => x, comparer))
        {
            if (!sourceFreq.TryGetValue(checkGroup.Key, out int count) || count < checkGroup.Count())
            {
                return false;
            }
        }
        return true;
    }
}

调用示例 #

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 };

Console.WriteLine(a.ContainsAll(b)); // 输出 True
Console.WriteLine(a.ContainsAll(c)); // 输出 False

多校验场景优化版本 #

如果需要用同一个主列表校验多个子列表，可以提前对主列表做一次频次统计，后续所有校验都复用统计结果，避免重复计算：

public static class ListExtension
{
    // 预处理主列表，得到可复用的频数字典
    public static Dictionary<T, int> GetFrequencyDict<T>(this List<T> source, IEqualityComparer<T> comparer = null)
    {
        comparer ??= EqualityComparer<T>.Default;
        return source.GroupBy(x => x, comparer)
                     .ToDictionary(g => g.Key, g => g.Count(), comparer);
    }

    // 用预处理好的频数字典做校验
    public static bool ContainsAllWithPreprocessedFreq<T>(this Dictionary<T, int> sourceFreq, List<T> toCheck, IEqualityComparer<T> comparer = null)
    {
        comparer ??= EqualityComparer<T>.Default;
        foreach (var checkGroup in toCheck.GroupBy(x => x, comparer))
        {
            if (!sourceFreq.TryGetValue(checkGroup.Key, out int count) || count < checkGroup.Count())
            {
                return false;
            }
        }
        return true;
    }
}

调用示例 #

List<int> mainList = new List<int> { 1, 2, 1, 3, 3, 3, 4 };
// 只需要预处理一次主列表
var mainFreq = mainList.GetFrequencyDict();

// 多次校验复用预处理结果
List<int> check1 = new List<int> { 1, 3, 3 };
List<int> check2 = new List<int> { 2, 2, 4 };

Console.WriteLine(mainFreq.ContainsAllWithPreprocessedFreq(check1)); // 输出 True
Console.WriteLine(mainFreq.ContainsAllWithPreprocessedFreq(check2)); // 输出 False

方案优势 #

• 时间复杂度为O(n+m)（n为主列表长度，m为待校验子列表长度），远高于逐个匹配删除的O(n*m)方案
• 不需要复制整个主列表，仅存储频次统计结果，空间效率更高，尤其适合元素重复率高的大列表
• 逻辑清晰易读，全靠内置函数实现，不需要手动写遍历匹配逻辑
• 支持自定义相等比较器，可适配自定义类型的校验需求

内容的提问来源于stack exchange，提问作者Rainbow-Anthony Lilico