来自两个列表（或阵列）的匹配项目

我遇到了一个问题，希望我的工作可以缩减到以下内容：我有两个List<int> s，我想查看是否有任何int s在ListA等于任何int在ListB。（它们可以是数组，如果这样可以让生活更轻松，但我认为List<>有一些内置的魔法可能会有所帮助。）我确信这是一个LINQ友好的问题，但我在2.0中工作。来自两个列表（或阵列）的匹配项目

我的解决方案至今，一直到foreach通过利斯塔，然后通过foreach数组listB，

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

这实际上是非常漂亮的，当他们每三个项目长，但现在他们是200长，他们经常不匹配，所以我们得到N^2比较的最坏情况。甚至有40,000次比较的速度非常快，但我认为我可能会错过一些东西，因为N^2对于这个特殊问题似乎很天真。

谢谢！

来源

2009-01-07 dnord

随着LINQ，这是微不足道的，因为你可以调用Intersect extension method上Enumerable class给你两个数组的交集：

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

您可以在推迟执行，像这样的扩展方法包装这件事

注意，这两种方法是（和我道歉，如果我在这里屠宰大O符号）O(N + M)其中N是第一个数组中的项目数，并M是项目的第二阵列中的数。您必须仅扫描一次每个列表，并且假定获取哈希代码并在哈希代码上执行查找是O(1)（常量）操作。

来源

2009-01-07 06:05:24 casperOne

如何使用BinarySearch方法而不是迭代内循环中的所有元素？

来源

2009-01-07 05:39:48 shahkalpesh

不是BinarySearch依靠被排序的列表吗？ http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx – 2009-01-07 06:45:21

将整个ListA加载到一个HashSet实例中，然后在ListB中对HastSet测试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>），并且始终因为您只对关键字感兴趣，所以将它存储为字典中的对象/值。

来源

2009-01-07 05:43:38 ChrisW

直到.NET 3.5才引入Hashset。 – casperOne 2009-01-07 06:00:29

散乱一般不是一个坏主意。如果有必要实施一个并不困难。 – PolyThinker 2009-01-07 06:07:04

在这种情况下，使用.Net 2.0，您可以使用Dictionary 而不是HashSet（因为您只对键感兴趣，所以始终将null作为对象/值存储在Dictionary中）。 – ChrisW 2009-01-07 06:08:09

而不是通过每个列表迭代的，看看在List.Contains方法：

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

来源

2009-01-07 05:53:51

克里斯给出的O通过散列（N）溶液。现在，根据常数因子（由于散列），可能值得考虑通过排序的O（N log（N））解决方案。根据您的使用情况，您可能会考虑几种不同的变体。

排序数组listB（O（N日志（N）），并使用搜索算法来解析在利斯塔每个元素（这又是O（N）* O（日志（N）））。
排序两者利斯塔和数组listB（O（N日志（N）），并使用一个O（N）的算法，以这些列表比较为重复。

如果两个列表将要使用多于一次，第二种方法是优选的。

来源

2009-01-07 06:04:59 PolyThinker

来自两个列表（或阵列）的匹配项目

回答

相关问题