具有重复的两个列表的交集

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

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

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 删除一些字典查找，但它牺牲了很多方法的优雅，所以我只是没有这样做的意愿。如果你关心性能，改变也不是坏事。

具有重复的两个列表的交集

Intersection of two lists with repetitions

c#

intersection

list