Пересечение массива VB.NET

Question

Это может быть ужасно тривиально, но у меня возникают проблемы с поиском ответа, который выполняется менее чем за n ^ 2 раза. Допустим, у меня есть два строковых массива, и я хочу знать, какие строки существуют в обоих массивах. Как бы я сделал это, эффективно, в VB.NET или есть ли способ сделать это, кроме двойного цикла?

Answer 1

Если вы сортируете оба массива, вы можете пройти через них каждый раз, чтобы найти все подходящие строки.

Псевдо-код:

while(index1 < list1.Length && index2 < list2.Length)
{
   if(list1[index1] == list2[index2])
   {
      // You've found a match
      index1++;
      index2++;
   } else if(list1[index1] < list2[index2]) {
      index1++;
   } else {
      index2++;
   }
}

Затем вы сократили время, необходимое для сортировки.

Answer 2

Простой способ (при условии, что нет .NET 3.5) - выгрузить строки из одного массива в хеш-таблицу, а затем перебрать другой массив, проверяя его по хеш-таблице. Это должно быть намного быстрее, чем поиск n ^ 2.

Answer 3

Если один из массивов отсортирован, вы можете выполнить бинарный поиск по нему во внутреннем цикле, это уменьшит время до O(n log n)

Answer 4

Сортировка обоих списков. Тогда вы можете с уверенностью знать, что если следующая запись в списке A - это «cobble», а следующая запись в списке B - «определенная», то «cobble» отсутствует в списке B. Просто переместите указатель / счетчик в любой список результат с более низким рейтингом и возрастание рейтинга.

Например:

Список 1: D, B, M, A, I
Список 2: I, A, P, N, D, G

отсортирован:

Список 1: A, B, D, I, M
Список 2: A, D, G, I, N, P

A против A -> сопоставить, сохранить A, продвинуть оба
B против D -> B D против D -> сопоставить, сохранить D, продвинуть оба
Я против G -> I> G, продвижение 2
I vs I -> матч, магазин I, продвижение обоих
М против Н -> М В списке 1 больше нет предметов, выход.
Список матчей A, D, I

2 списка сортирует O (n log (n)), плюс сравнение O (n) делает это O (n (log (n) + 1)).