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

Question

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

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

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

Предложения высоко оценены!

Answer 1

Попробуйте

var diff = oldKeys.Except(currKeys); 

Это требует C# 3.0

Answer 2

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

Answer 3

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

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

Получит эти, а также.

Answer 4

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

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

Алгоритм, который

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