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

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

Загрузите весь 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 как объект / значение в Словаре, поскольку вас интересуют только ключи.

Вместо того, чтобы перебирать каждый список, взгляните на метод List.Contains:

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

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

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

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

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

С LINQ это тривиально, так как вы можете вызвать Intersect метод расширения на Enumerable класс, чтобы получить заданное пересечение двух массивов:

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