Сопоставление элементов из двух списков (или массивов)

Ответ 1

С LINQ это тривиально, так как вы можете вызвать Intersect метод расширения в 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);
    }
}

Вы можете обернуть это в метод расширения, который отменяет выполнение следующим образом:

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) (постоянная).

Ответ 2

Загрузите весь ListA в экземпляр HashSet, а затем проверьте элемент foreach в ListB на HastSet: я уверен, что это будет 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 как объект/значение в словаре, поскольку вы только заинтересованных в ключах.

Ответ 3

Вместо повторения каждого списка взгляните на метод List.Contains:

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

Ответ 4

Крис дает решение O (N) путем хеширования. Теперь, в зависимости от постоянного фактора (из-за хэширования), можно было бы рассмотреть решение O (N log (N)) путем сортировки. Существует несколько различных вариантов, которые вы можете учитывать в зависимости от вашего варианта использования.

• Сортировать ListB (O (N log (N)) и использовать алгоритм поиска для анализа каждого элемента в ListA (который снова является O (N) * O (log (N))).

• Сортируйте ListA и ListB (O (N log (N)) и используйте алгоритм O (N) для сравнения этих списков для дубликатов.

Если оба списка будут использоваться более одного раза, предпочтительнее второй метод.

Ответ 5

Как использовать метод BinarySearch вместо итерации по всем элементам во внутреннем цикле?