使用 LINQ,这很简单,因为你可以在Enumerable
类上调用Intersect
扩展方法,以给出两个数组的交集:
var intersection = ListA.Intersect(ListB)
然而,这是一种
集合交集,意味着如果
ListA
和
ListB
中没有唯一值,你将不会得到任何副本。换句话说,如果你有以下内容:
var ListA = new [] { 0, 0, 1, 2, 3 };
var ListB = new [] { 0, 0, 0, 2 };
然后ListA.Intersect(ListB)
会产生:
{ 0, 2 }
如果您期望:
{ 0, 0, 2 }
那么您需要自己维护一个计数器,在扫描这两个列表时进行递增/递减操作。
首先,您需要使用
Dictionary<TKey, int>
来收集各个项目的列表:
var countsOfA = ListA.GroupBy(i => i).ToDictionary(g => g.Key, g => g.Count())
从那里开始,您可以扫描ListB
,并在遇到countsOfA
中的项目时将其放入列表中:
IList<int> matched = new List<int>();
foreach (int b in ListB)
{
int count;
if (countsOfA.TryGetValue(b, out count))
{
Debug.Assert(count > 0);
matched.Add(b);
if (--count == 0) countsOfA.Remove(b);
}
}
您可以将此封装在延迟执行的扩展方法中,如下所示:
public static IEnumerable<T> MultisetIntersect(this IEnumerable<T> first,
IEnumerable<T> second)
{
return first.MultisetIntersect(second, EqualityComparer<T>.Default);
}
public static IEnumerable<T> MultisetIntersect(this IEnumerable<T> first,
IEnumerable<T> second, IEqualityComparer<T> comparer)
{
if (first == null) throw new ArgumentNullException("first");
if (second == null) throw new ArgumentNullException("second");
if (comparer == null) throw new ArgumentNullException("comparer");
return first.MultisetIntersectImplementation(second, comparer);
}
private static IEnumerable<T> MultisetIntersectImplementation(
this IEnumerable<T> first, IEnumerable<T> second,
IEqualityComparer<T> comparer)
{
Debug.Assert(first != null);
Debug.Assert(second != null);
Debug.Assert(comparer != null);
IDictionary<T, long> counts = first.GroupBy(t => t, comparer).
ToDictionary(g => g.Key, g.LongCount(), comparer);
foreach (T t in second)
{
long count;
if (counts.TryGetValue(t, out count))
{
Debug.Assert(count > 0);
yield return t;
if (--count == 0) counts.Remove(t);
}
}
}
请注意,这两种方法都是(如果我在此混淆了大O符号表示法,则向您道歉)
O(N + M)
,其中
N
是第一个数组中的项目数,而
M
是第二个数组中的项目数。您只需扫描每个列表一次,并且假定获取哈希码并在哈希码上执行查找是
O(1)
(常量)操作。
Intersect
以及满足在集合与多重集合上使用交集的期望。 - casperOne