Алгоритм сравнения

Question

У меня есть 2 массива (A и B), которые содержат похожие данные с некоторыми отличиями. Я хотел бы вернуть массив объектов, которые только в A и другой массив объектов, которые только в B. До сих пор я думал:

1. Грубая сила с некоторыми оптимизациями (это тривиально)
2. Сортировка массивов и использование бинарного поиска.

Какие у меня есть другие варианты? Любые языки / решения являются честной игрой.

Answer 1

Вы можете отсортировать оба массива, а затем выполнить линейное сканирование обоих массивов одновременно. Это будет алгоритм O (nlogn) для сортировки и O (n) для сканирования / построения новых массивов.

Answer 2

Я бы поместил элементы массива A в хеш-таблицу, затем перебрал бы массив B, выполняя поиск в хэш-таблице, чтобы эффективно определить, какие элементы в B также находятся в A. перебирая массив A. Это будет O (N) на всем протяжении.

Answer 3

Многое зависит от того, какой тип данных у вас есть. Вы упомянули сортировку, поэтому я считаю, что элементы сопоставимы. Для наборов размером m и n для сортировки потребуется O(m lg m + n lg n), и это будет доминировать. (Асимптотически, не имеет значения, выполняете ли вы бинарный поиск или обходите оба списка. Обход обоих списков должен быть O( m + n).) Конечно, если вы используете данные с лучшим алгоритмом сортировки, например, целые числа с radix-sort , вы должны быть в состоянии опуститься до O( m + n).

Использование наборов (как предлагают другие) неявно предполагает использование хеширования, что определенно облегчит вашу проблему. Если вы хэшируете все элементы в A (O(m)) и сохраняете все хэши в хэш-наборе в памяти, то хеш-код B (O(n)) и обнаруживает, где в хэш-наборе могут возникать коллизии. Это становится вопросом оптимизации: вы должны оценить классический компромисс между скоростью и памятью. Чем больше ваш хэш-набор, тем быстрее будут проверяться коллизии. Это будет работать в O( m + n ).

Стоит отметить, что вы можете доказать, что любой алгоритм, который выполняет то, что вы запрашиваете, будет запущен как минимум за m + n время, так как нужно просмотреть все входные данные.

Answer 4

У меня нет реализации или алгоритма сверх того, что уже было сказано, но я решил оставить это решение в c # / linq для всех, кто может найти этот вопрос и хочет сделать это:

    var a = new int[] { 1, 2, 3, 6, 7, 8, 9, 10 };
    var b = new int[] { 1, 2, 3, 4, 5, 6, 7 };

    int[] addedToA = a.Except(b);
    int[] missingFromA = b.Except(a);

    foreach (var i in addedToA)
    {
        Console.Write("{0} ", i);
    }
    Console.WriteLine();
    foreach (var i in missingFromA)
    {
        Console.Write("{0} ", i);
    }

Это печатает:

8 9 10
4 5

Answer 5

Попробуйте использовать наборы. У них обычно есть метод Difference () (или что-то вроде этого), который возвращает именно то, что вы хотите. Просто как тот. Как только это не зависит от языка, то, как вы создаете наборы или преобразовываете разницу в массив, делается с помощью общих методов.

Set A = createSetA();
Set B = createSetB();

Array onlyAElements = transformToArray(A.difference(B));
Array onlyBElements = transformToArray(B.difference(A));

Кроме того, вы можете отсортировать оба массива и получить оба разностных массива одновременно. Что-то вроде

int aIndex = 0;
int bIndex = 0;

Array aOnly = new Array();
Array bOnly = new Array();

while (aIndex != a.length || bIndex != b.length)
{
   if (A[aIndex] == B[bIndex]
   {
       aIndex++;
       bIndex++;
   }
   else if (A[aIndex] > B[bIndex])
   {
       aOnly.add(A[aIndex]);
       aIndex++;
   }
   else 
   {
       bOnly.add(B[bIndex]);
       bIndex++;
   }
} 

Вы должны помнить, что есть некоторые ошибки при выходе за пределы. Но код только для того, чтобы понять основную идею.