Алгоритм нахождения разницы между двумя массивами

Question

Учитывая два массива, существует ли быстрый алгоритм для нахождения всех элементов в двух, которые отличаются? Например, рассмотрим два массива клавиш (как в клавишах). Одна представляет в настоящий момент нажатые клавиши, а другая представляет клавиши, нажатые в последний шаг времени.

Keys[] oldKeys = LastKeyboardState.GetPressedKeys();
Keys[] currKeys = CurrentKeyboardState.GetPressedKeys();

// the user just pressed these key(s) during the last timestep.
Keys[] diff = ...

Предложения очень ценятся!

Answer 1

Ну, алгоритм грубой силы был бы m * n, где m и n - размеры ваших двух массивов.

Если вы используете какой-либо вид дерева вместо линейного массива, тогда ваше время падает до m * log2 (n)

Алгоритм для этого

foreach(key ok in oldkeys)
{
    if(!oldKeys.Contains(ok))
    {
        diff.add(ok);
    }
}
foreach(key nk in newkeys)
{
    if(!newKeys.Contains(nk))
    {
        diff.add(nk);
    }
}

Answer 2

Попробуйте это

var diff = oldKeys.Except(currKeys);

Для этого требуется C # 3.0

Answer 3

В продолжение на JaredPar: это покажет ключи только в oldKeys, но не в currKeys. Поэтому, если A находится в currKeys, но не в oldKeys, оно не будет отображаться в diff.

var diff = oldKeys.Union(currKeys).Except(currKeys.Intersect(oldKeys))

Получит и их.

Answer 4

Два битовых поля, запустите двоичный XOR. Все, что у вас осталось, это то, что вы хотите.