如何进行整数列表交集并保留重复项？

Question

我正在处理一个最大公约数和最小公倍数的任务，需要列出它们的公因数。Intersection()方法不能使用，因为它会移除重复项。Contains()方法也不能使用，因为它会返回第一个列表中与第二个列表匹配的所有整数。有没有一种交集的方法不会移除重复项呢？

编辑：很抱歉没有提供示例，下面是我的意思：

如果我有这些集合：

{1, 2, 2, 2, 3, 3, 4, 5}
{1, 1, 2, 2, 3, 3, 3, 4, 4}

我希望得到输出

{1, 2, 2, 3, 3, 4}

- DuckReconMajor

---

如果a是{3,3,3,3}，b是{3,3}，你预计输出中会有多少个3？2、4还是6？ - Ani

我认为下面的答案混淆了问题。 正确的问题是“找出两个集合的交集”。 问题在于“Intersect”运算符会删除重复项 - 不要删除重复项解决问题。 - Kirk Broadhurst

为什么？那样可以去除重复项。请解释你的逻辑。 - Jonathan Grynspan

当然，它不会删除重复项，两个3直接来自交集操作，绝对没有删除重复项！ - user1935724

或者您可以参考集合交集操作的基本定义。 - user1935724

一个集合不能有重复的值（无论是在数学上还是在C#中），所以你那里的不是集合。 - Andy

Answer 1

我编写了这个扩展来解决这个问题：

public static IEnumerable<T> Supersect<T>(this IEnumerable<T> a, ICollection<T> b)
              => a.Where(b.Remove);

例子：

var a = new List<int> { 1, 2, 2, 2, 3, 3, 4, 5 };
var b = new List<int> { 1, 1, 2, 2, 3, 3, 3, 4, 4};

var result = a.Supersect(b);

结果：

{ 1, 2, 2, 3, 3, 4 }

- Joep Geevers

---

我喜欢这个，但它会通过清空b来改变它。 - Porco

Answer 2

ILookup<int, int> lookup1 = list1.ToLookup(i => i);
ILookup<int, int> lookup2 = list2.ToLookup(i => i);

int[] result =
(
  from group1 in lookup1
  let group2 = lookup2[group1.Key]
  where group2.Any()
  let smallerGroup = group1.Count() < group2.Count() ? group1 : group2
  from i in smallerGroup
  select i
).ToArray();

技术上讲，where表达式是可选的，但我认为它可以更清晰地表达意图。

---

如果您想要更简洁的代码：

ILookup<int, int> lookup2 = list2.ToLookup(i => i);

int[] result =
(
  from group1 in list1.GroupBy(i => i)
  let group2 = lookup2[group1.Key]
  from i in (group1.Count() < group2.Count() ? group1 : group2)
  select i
).ToArray();

- Amy B

---

+1 我想起了我们两个都回答过的这个问题 :) https://dev59.com/xm855IYBdhLWcg3wPBpx - Ani

@DuckReconMajor，我的答案避免完全计算两个匹配组，这应该会更好，不过已经晚了三年 :-) https://dev59.com/1m445IYBdhLWcg3wJ298#21776543 - Jodrell

Answer 3

您可以使用我为另一个答案编写的通用扩展，它本质上是一个单一的Linq语句。请注意，它使用Zip来避免不必要的完整匹配组枚举。

public static IEnumerable<T> Commom<T>(
        this IEnumerable<T> source,
        IEnumerable<T> sequence,
        IEqualityComparer<T> comparer = null)
{
    if (sequence == null)
    {
        return Enumerable.Empty<T>();
    }

    if (comparer == null)
    {
        comparer = EqualityComparer<T>.Default;
    }

    return source.GroupBy(t => t, comparer)
        .Join(
            sequence.GroupBy(t => t, comparer),
            g => g.Key,
            g => g.Key,
            (lg, rg) => lg.Zip(rg, (l, r) => l),
            comparer)
        .SelectMany(g => g);
}

这使得...

new[] {1, 2, 2, 2, 3, 3, 4, 5}.Common(
    new[] {1, 1, 2, 2, 3, 3, 3, 4, 4}).ToArray()

保持源序列的顺序，按照所需的方式。

- Jodrell

Answer 4

你是否在寻找类似这样的东西？它应该是相当接近 O(n+m) 的，其中 n 是 first 中项目的数量，m 是 second 中项目的数量。

public static IEnumerable<T> Overlap<T>(this IEnumerable<T> first,
    IEnumerable<T> second, IEqualityComparer<T> comparer = null)
{
    // argument checking, optimisations etc removed for brevity

    var dict = new Dictionary<T, int>(comparer);

    foreach (T item in second)
    {
        int hits;
        dict.TryGetValue(item, out hits);
        dict[item] = hits + 1;
    }

    foreach (T item in first)
    {
        int hits;
        dict.TryGetValue(item, out hits);
        if (hits > 0)
        {
            yield return item;
            dict[item] = hits - 1;
        }
    }
}

- LukeH

Answer 5

• 找到两个列表的交集。
• 通过交集项对列表进行分组
• 合并分组，并选择每个项目的Min(Count)
• 将其展开成一个新列表。

请参见下文：

var intersect = list1.Intersect(list2).ToList();
var groups1 = list1.Where(e => intersect.Contains(e)).GroupBy(e => e);
var groups2 = list2.Where(e => intersect.Contains(e)).GroupBy(e => e);

var allGroups = groups1.Concat(groups2);

return allGroups.GroupBy(e => e.Key)
    .SelectMany(group => group
        .First(g => g.Count() == group.Min(g1 => g1.Count())))
    .ToList();

- Kirk Broadhurst

Answer 6

这是一种实现方法。公平地说，它与David B的答案非常相似，只是使用了join来进行关联。

IEnumerable<Foo> seqA = ...
IEnumerable<Foo> seqB = ...

var result = from aGroup in seqA.GroupBy(x => x)
             join bGroup in seqB.GroupBy(x => x) 
                         on aGroup.Key equals bGroup.Key
             let smallerGroup = aGroup.Count() < bGroup.Count() 
                                ? aGroup : bGroup
             from item in smallerGroup
             select item;

- Ani