两个列表（或数组）中的匹配项

Question

我在工作中遇到了一个问题，希望能简化为以下问题：我有两个 List<int>，我想知道 ListA 中的任何一个 int 是否等于 ListB 中的任何一个 int。（如果可以的话，它们可以是数组，但我认为 List<> 有一些内置魔力可能会有所帮助。）我确定这是一个适合使用 LINQ 的问题，但我正在使用 2.0 版本。

到目前为止，我的解决方案是通过 foreach 遍历 ListA，然后再通过 foreach 遍历 ListB。

foreach (int a in ListA)
{
    foreach (int b in ListB)
    {
        if (a == b)
        {
            return true;
        }
    }
}

当每个项目只有三个时，这实际上非常流畅，但现在每个项目都有200个，而且它们经常不匹配，因此我们得到最坏的N^2比较情况。即使进行40000次比较也很快，但我认为我可能漏掉了什么，因为N^2对于这个特定问题似乎太幼稚了。

谢谢！

- dnord

Answer 1

使用 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中的项目时将其放入列表中：

// The items that match.
IList<int> matched = new List<int>();

// Scan 
foreach (int b in ListB)
{
    // The count.
    int count;

    // If the item is found in a.
    if (countsOfA.TryGetValue(b, out count))
    {
        // This is positive.
        Debug.Assert(count > 0);

        // Add the item to the list.
        matched.Add(b);

        // Decrement the count.  If
        // 0, remove.
        if (--count == 0) countsOfA.Remove(b);
    }
}

您可以将此封装在延迟执行的扩展方法中，如下所示：

public static IEnumerable<T> MultisetIntersect(this IEnumerable<T> first,
    IEnumerable<T> second)
{
    // Call the overload with the default comparer.
    return first.MultisetIntersect(second, EqualityComparer<T>.Default);
}

public static IEnumerable<T> MultisetIntersect(this IEnumerable<T> first,
    IEnumerable<T> second, IEqualityComparer<T> comparer)
{
    // Validate parameters.  Do this separately so check
    // is performed immediately, and not when execution
    // takes place.
    if (first == null) throw new ArgumentNullException("first");
    if (second == null) throw new ArgumentNullException("second");
    if (comparer == null) throw new ArgumentNullException("comparer");

    // Defer execution on the internal
    // instance.
    return first.MultisetIntersectImplementation(second, comparer);
}

private static IEnumerable<T> MultisetIntersectImplementation(
    this IEnumerable<T> first, IEnumerable<T> second, 
    IEqualityComparer<T> comparer)
{
    // Validate parameters.
    Debug.Assert(first != null);
    Debug.Assert(second != null);
    Debug.Assert(comparer != null);

    // Get the dictionary of the first.
    IDictionary<T, long> counts = first.GroupBy(t => t, comparer).
        ToDictionary(g => g.Key, g.LongCount(), comparer);

    // Scan 
    foreach (T t in second)
    {
        // The count.
        long count;

        // If the item is found in a.
        if (counts.TryGetValue(t, out count))
        {
            // This is positive.
            Debug.Assert(count > 0);

            // Yield the item.
            yield return t;

            // Decrement the count.  If
            // 0, remove.
            if (--count == 0) counts.Remove(t);
        }
    }
}

请注意，这两种方法都是（如果我在此混淆了大O符号表示法，则向您道歉） O（N + M），其中N是第一个数组中的项目数，而M是第二个数组中的项目数。您只需扫描每个列表一次，并且假定获取哈希码并在哈希码上执行查找是O（1）（常量）操作。

- casperOne

---

Enumerable.Intersect采用类似的方法吗？ - palswim

@palswim 稍微有些不一样。我已经更新了我的答案以反映“Intersect”，稍后我会提供一个更详细的答案，并附上计数。 - casperOne

@palswim 更新了答案，反映出在使用交集时，使用Intersect以及满足在集合与多重集合上使用交集的期望。 - casperOne

Answer 2

将ListA的所有内容加载到一个HashSet实例中，然后测试ListB中的每个项是否与HashSet匹配：我相信这应该是O(N)。

//untested code ahead
HashSet<int> hashSet = new HashSet<int>(ListA);
foreach (int i in ListB)
{
    if (hashSet.Contains(i))
        return true;
}

以下是同样的内容，只不过在一行中：

return new HashSet<int>(ListA).Overlaps(ListB);

在.NET 3.5中没有HashSet，因此在.NET 2.0中，您可以使用Dictionary<int,object>替代HashSet<int>，并始终将null作为字典中的对象/值存储，因为您只关心键。

- Chris

---

Hashset 直到 .NET 3.5 才被引入。 - casperOne

哈希算法一般来说并不是一个坏主意。如果必要的话，实现一个也不难。 - PolyThinker

在这种情况下，使用.Net 2.0，您可以使用Dictionary<int,object>代替HashSet（并始终将null存储为字典中的对象/值，因为您只对键感兴趣）。 - ChrisW

对于我的情况，这是最好的解决方案。谢谢 @ChrisW - TuanTDA

Answer 3

不要遍历每个列表，可以使用List.Contains方法：

foreach (int a in ListA)
{
  if (ListB.Contains(a))
    return true;
}

- Metro Smurf

---

这并不比原来的解决方案更好：仍然是O(N^2)。 - ChrisW

教我在睡前发布...更深入地了解Contains方法后，它确实执行了列表的内部迭代。在这种情况下，使用Dictionary对象可能是更好的选择。 - Metro Smurf

Answer 4

克里斯提供了一种哈希的O(N)解决方案。现在，根据常数因子（由于哈希），考虑排序的O(N log(N))解决方案可能值得考虑。根据您的用例，有几个不同的变体可供考虑。

1. 对ListB进行排序（O(N log(N)）），并使用搜索算法解析ListA中的每个元素（再次为O(N) * O(log(N))）。
2. 对ListA和ListB进行排序（O(N log(N)），并使用O(N)算法比较这些列表以查找重复项。

如果两个列表都将被多次使用，则更喜欢第二种方法。

- PolyThinker

Answer 5

使用二分查找方法代替在内部循环中迭代所有元素怎么样？

- shahkalpesh

---

二分查找不依赖于列表的排序吗？http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx - Fabrizio C.