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

Question

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

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

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

Answer 1

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

Answer 2

Попробуйте использовать наборы. Обычно они имеют метод 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++; 
    } 
} 

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

Answer 3

не имеет реализации или алгоритм сверх того, что уже было сказано, но я думал, что я хотел бы оставить это решение в 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 4

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

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

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

Answer 5

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