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

26 浏览
0 Comments

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

我在我的工作中遇到了一个问题，希望能够简化成以下几点：我有两个List，我想要判断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似乎太简单了。

谢谢！

0

3 答案

0 Comments

原因：该问题出现的原因是原始解决方案的时间复杂度为O(N^2)，即需要对两个列表进行嵌套循环迭代，效率较低。

解决方法：通过使用List.Contains方法来改进解决方案，在列表A的每个元素中判断列表B是否包含该元素。但是，这种方法仍然需要对列表B进行迭代，时间复杂度仍为O(N^2)，效率不高。

为了改善效率，可以使用Dictionary对象来解决这个问题。使用Dictionary对象可以将列表B的元素作为键，然后在列表A中进行查找，从而实现快速的匹配操作。

以下是使用Dictionary对象进行匹配的代码示例：

Dictionary dictionaryB = new Dictionary();
foreach (int b in ListB)
{
  dictionaryB[b] = true;
}
foreach (int a in ListA)
{
  if (dictionaryB.ContainsKey(a))
    return true;
}

通过将列表B的元素作为字典的键，可以通过字典的ContainsKey方法来判断列表A中的元素是否存在于字典中，从而实现更高效的匹配操作。这种方法的时间复杂度为O(N)，效率较高。

通过使用Dictionary对象来替代原始解决方案中的嵌套循环迭代，可以实现更高效的匹配操作，提高代码的执行效率。

0
0 Comments

问题的出现的原因是需要从两个列表（或数组）中匹配相同的项。解决方法是使用LINQ的Intersect方法来获取两个数组的交集。然而，这只是一个集合的交集，如果ListA和ListB中没有唯一的值，将不会得到任何副本。如果ListA和ListB分别是[0, 0, 1, 2, 3]和[0, 0, 0, 2]，ListA.Intersect(ListB)将产生[0, 2]，而不是[0, 0, 2]。为了获取预期的结果，需要自己维护项的计数，并在扫描两个列表时逐渐减少。首先，可以使用Dictionary收集每个项的计数：

var countsOfA = ListA.GroupBy(i => i).ToDictionary(g => g.Key, g => g.Count());

然后，可以扫描ListB，并在countsOfA中找到匹配的项：

IList matched = new List();

foreach (int b in ListB)

{

int count;

if (countsOfA.TryGetValue(b, out count))

{

Debug.Assert(count > 0);

matched.Add(b);

if (--count == 0) countsOfA.Remove(b);

}

}

可以将这个方法封装成一个延迟执行的扩展方法：

public static IEnumerable MultisetIntersect(this IEnumerable first,

IEnumerable second)

{

return first.MultisetIntersect(second, EqualityComparer.Default);

}

public static IEnumerable MultisetIntersect(this IEnumerable first,

IEnumerable second, IEqualityComparer comparer)

{

if (first == null) throw new ArgumentNullException("first");

if (second == null) throw new ArgumentNullException("second");

if (comparer == null) throw new ArgumentNullException("comparer");

return first.MultisetIntersectImplementation(second, comparer);

}

private static IEnumerable MultisetIntersectImplementation(

this IEnumerable first, IEnumerable second,

IEqualityComparer comparer)

{

Debug.Assert(first != null);

Debug.Assert(second != null);

Debug.Assert(comparer != null);

IDictionary counts = first.GroupBy(t => t, comparer)

.ToDictionary(g => g.Key, g.LongCount(), comparer);

foreach (T t in second)

{

long count;

if (counts.TryGetValue(t, out count))

{

Debug.Assert(count > 0);

yield return t;

if (--count == 0) counts.Remove(t);

}

}

}

需要注意的是，这两种方法的时间复杂度都是O(N + M)，其中N是第一个数组中的项数，M是第二个数组中的项数。每个列表只需扫描一次，并且假设获取哈希码和进行哈希码查找是一个O(1)（常数）的操作。Enumerable.Intersect方法采用了类似的方法，但不完全相同。

0
0 Comments

问题的出现原因是需要从两个列表（或数组）中找出相匹配的项。解决方法是使用哈希集合（HashSet）来进行匹配。首先将ListA中的所有项加载到一个HashSet实例中，然后对ListB中的每个项进行哈希集合的匹配。如果匹配成功，则返回true。

在代码示例中，使用了C#语言来实现这个解决方法。首先创建一个HashSet实例，并将ListA作为参数传入。然后使用foreach循环遍历ListB中的每个项，在HashSet中使用Contains方法进行匹配。如果匹配成功，则返回true。

除了上述的代码示例之外，还可以使用一行代码来实现相同的功能。直接返回一个HashSet实例与ListB进行重叠判断的结果。

然而，在.NET 3.5之前的版本中，并没有HashSet类可用。在.NET 2.0中，可以使用Dictionary代替HashSet，并且始终将null作为字典中的值存储，因为只关注键值。

问题的解决方法是使用哈希集合进行匹配。在.NET 3.5及以上版本中，可以直接使用HashSet类来实现。在.NET 2.0中，可以使用Dictionary类来替代HashSet，并将null作为值存储。哈希集合的使用可有效地进行匹配操作。

0