匹配两个列表(或数组)中的项

Question

我的工作有问题希望减少到以下内容:我有两个List<int>s,我想看看是否有任何ints in ListA等于任何intin ListB.(它们可以是阵列,如果这样可以让生活变得更轻松,但我认为它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比较的最坏情况.即使是40,000次比较也相当快,但我想我可能会遗漏一些东西,因为N ^ 2对于这个特殊问题似乎很天真.

谢谢!

Answer 1

使用LINQ,这是微不足道的,因为您可以在类上调用Intersect扩展方法来为您提供两个数组的集合交集:Enumerable

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);
        }
    }
}

请注意,这两种方法都是(如果我在这里屠宰Big-O表示法,我道歉)O(N + M),N第一个数组中M的项目数是多少,第二个数组中的项目数是多少.您必须只扫描每个列表一次,并且假设获取哈希码并对哈希码执行查找是O(1)(常量)操作.

Answer 2

将整个ListA加载到HashSet实例中,然后针对HastSet测试ListB中的foreach项:我很确定这将是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);

HashSet在.NET 3.5中不存在,因此在.NET 2.0中您可以使用Dictionary<int,object>(而不是使用HashSet<int>),并始终将null存储为Dictionary中的对象/值,因为您只对键感兴趣.