两个列表的交集与重复

Question

我正在尝试创建一个函数,它会给我两个列表的交集,考虑到可以有重复的项目,我需要它们在输出中.

Console.Write((new[] {1, 2, 2, 3}).Intersect(new[] {1, 2, 2}));

只输出{1,2},我需要的输出是{1,2,2}.

这是我创建的方法:

private static IEnumerable<int> IntersectWithRepetitons(List<int> a, List<int> b)
{
    if (!a.Any() || !b.Any()) return Enumerable.Empty<int>();
    if (a.Count() > b.Count()) return IntersectWithRepetitons(b, a);

    var idx = b.IndexOf(a.First());
    if (idx < 0) return IntersectWithRepetitons(b, a.Skip(1).ToList());

    var tmp1 = new List<int> { a.First() };
    var tmp2 = new List<int>(b);
    tmp2.RemoveAt(idx);
    return tmp1.Concat(IntersectWithRepetitons(tmp2, a.Skip(1).ToList()));
}

我确信这可以高度优化但是,我主要担心(效率明智)是为了保持输入列表完好无损,当我从中删除找到的项目时,我必须复制'b'列表:

var tmp2 = new List<int>(b);
tmp2.RemoveAt(idx);

并且每次递归调用都会发生这种情况.任何想法或想法将非常感激.谢谢.

Answer 1

将其中一个序列映射到项目字典到它们出现的次数,然后对于另一个序列中的每个项目,如果它在集合中,并且查找的值大于零,则产生它和decriment:

public static IEnumerable<T> IntersectWithRepetitons<T>(this IEnumerable<T> first,
    IEnumerable<T> second)
{
    var lookup = second.GroupBy(x => x)
        .ToDictionary(group => group.Key, group => group.Count());
    foreach (var item in first)
        if (lookup.ContainsKey(item) && lookup[item] > 0)
        {
            yield return item;
            lookup[item]--;
        }
}

这确保了项目在两个集合中每次重复时都是收益.

您可以使用TryGetValue删除一些字典查找,但它牺牲了很多方法的优雅,所以我只是没有在我这样做.如果你关心性能,那么改变并不是件坏事.