Với LINQ, đây là tầm thường, như bạn có thể gọi Intersect extension method trên Enumerable class để cung cấp cho bạn giao bộ của hai mảng:
var intersection = ListA.Intersect(ListB);
Tuy nhiên, đây là thiết ngã tư, có nghĩa là nếu ListA và ListB không có giá trị duy nhất trong đó, bạn sẽ không nhận được bất kỳ bản sao nào. Nói cách khác, nếu bạn đã điều sau đây:
var ListA = new [] { 0, 0, 1, 2, 3 };
var ListB = new [] { 0, 0, 0, 2 };
Sau đó ListA.Intersect(ListB) sản xuất:
{ 0, 2 }
Nếu bạn đang mong:
{ 0, 0, 2 }
Sau đó, bạn sẽ phải duy trì một đếm các mục của bản thân và năng suất/giảm khi bạn quét hai danh sách.
Thứ nhất, bạn muốn thu thập một Dictionary<TKey, int> với danh sách các mặt hàng cá nhân:
var countsOfA = ListA.GroupBy(i => i).ToDictionary(g => g.Key, g => g.Count());
Từ đó, bạn có thể quét ListB và đặt rằng trong một danh sách khi bạn gặp một mục trong 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);
}
}
Bạn có thể quấn này trong một phương pháp mở rộng mà trì hoãn thực hiện như sau:
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);
}
}
}
Lưu ý rằng cả hai cách tiếp cận này là (và tôi xin lỗi nếu tôi đang ký hiệu Big-O ở đây) O(N + M) trong đó N là số mục trong mảng đầu tiên và M là số mục trong mảng thứ hai . Bạn phải quét từng danh sách một lần và giả định rằng việc nhận mã băm và thực hiện tra cứu trên mã băm là hoạt động O(1) (hằng số).
[Enumerable.Intersect] (http://stackoverflow.com/a/10627437/393280) có cách tiếp cận tương tự không? – palswim
@palswim Hơi, nhưng không chính xác. Tôi đã cập nhật câu trả lời của tôi để phản ánh 'Intersect' và tôi sẽ cập nhật với một câu trả lời kỹ lưỡng hơn có số lượng trong một chút. – casperOne
@palswim Cập nhật câu trả lời để phản ánh bằng cách sử dụng 'Giao nhau' cũng như mong đợi cuộc họp khi sử dụng giao điểm trên một tập hợp so với số nhiều. – casperOne