Con LINQ, esto es trivial, como se puede llamar a la Intersect extension method en el Enumerable class para darle la intersección de conjuntos de las dos matrices:
var intersection = ListA.Intersect(ListB);
Sin embargo, este es el conjunto intersección, es decir, si ListA y ListB no tienen valores únicos, no obtendrá ninguna copia. En otras palabras, si tiene lo siguiente:
var ListA = new [] { 0, 0, 1, 2, 3 };
var ListB = new [] { 0, 0, 0, 2 };
Entonces ListA.Intersect(ListB) produce:
{ 0, 2 }
Si usted está esperando:
{ 0, 0, 2 }
Entonces vas a tener que mantener una cuente los artículos usted mismo y ceda/disminuya mientras escanea las dos listas.
En primer lugar, usted quiere recoger una Dictionary<TKey, int> con las listas de los artículos individuales:
var countsOfA = ListA.GroupBy(i => i).ToDictionary(g => g.Key, g => g.Count());
A partir de ahí, puede escanear ListB y el lugar que en una lista cuando se encuentra con un elemento en 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);
}
}
Usted puede terminar con esto en un método de extensión que se aplaza la ejecución de este modo:
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);
}
}
}
Tenga en cuenta que estos dos enfoques son (y me disculpo si estoy carnicería Big-O notación aquí) O(N + M) donde N es el número de elementos de la primera serie, y M es el número de elementos de la segunda matriz . Debe escanear cada lista solo una vez, y se supone que obtener los códigos hash y realizar búsquedas en los códigos hash es una operación O(1) (constante).
¿[Enumerable.Intersect] (http://stackoverflow.com/a/10627437/393280) adopta un enfoque similar? – palswim
@palswim Ligeramente, pero no exactamente. He actualizado mi respuesta para que refleje 'Intersecar' y la actualizaré con una respuesta más completa que cuenta un poco los conteos. – casperOne
@palswim Se actualizó la respuesta para reflejar el uso de 'Intersecar', así como las expectativas de la reunión cuando se usan las intersecciones en un conjunto frente a un conjunto múltiple. – casperOne