c#有效的包含重复项的ContainsAll ?

Question

类似于现有的"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:我需要检查在大列表中找到的每个元素的数量至少与在小列表中找到的元素一样多。不仅两个链表中都有多个，而且小链表中的每个元素都可以与大链表中的唯一元素配对。

我没有具体的性能要求。我只是想知道是否有更"正确"的。比手工检查的方式。你可以说这是"正确的"可能意味着更快，或者更可读，或者仅仅是通过使用内置函数更容易编写。也许没有更好的办法。我将补充说，我的用例可能涉及到根据几个较小的列表检查较大的列表，因此较大列表的一次性转换(例如:

Answer 1

您可以对两个列表中的每个元素进行计数，然后检查l2中所有元素的计数是否小于或等于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)

Answer 2

如果您对a进行查找，那么您可以询问它是否包含b的所有大于或等于计数的键

var al = a.ToLookup(x=>x);
return b.ToLookup(x=>x).All(ble => al.Contains(ble.Key) && al[ble.Key].Count() >= ble.Count());

你可以通过只构建一组计数来优化它，然后检查它是否可以"支付"。对于第二组值

var d = new Dictionary<int, int>();
a.ForEach(x => { if(d.ContainsKey(x)) d[x]++; else d[x] = 1;});
b.ForEach(x => { if(--d[x] < 0) throw new Exception($"More {x} in B than A"); });

后一行代码可能发生以下两种情况之一:

• 从a构建的字典不包含来自b的键-出现keynotfoundexception
• 计数下降到0以下(--d[x]返回存储在字典中的新值)。如果为负，则b中的键x多于a，并产生不同的异常

因此，如果出现异常，b不是a的子集，如果不是，它就是

如果你想的话，你可以将第二个ForEach扩展为ForEach循环，并在循环内执行if(!d.ContainsKey(x) || --d[x] < 0) return false;，在循环外执行return true，从而将其更改为无例外。