Algorithm for finding the difference between two arrays

Question

Given two arrays, is there a quick algorithm for finding all elements in two different ones? For example, consider two arrays of Keys structures (as in a keyboard). One represents the current keys pressed, and the other represents the keys pressed in the last time interval.

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

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

Suggestions are greatly appreciated!

Answer 1

try it

var diff = oldKeys.Except(currKeys);

This requires C # 3.0

Answer 2

Well, the brute force algorithm will be m * n, where m and n are the sizes of your two arrays.

If you use any tree instead of a linear array, your time falls to m * log2 (n)

Algorithm for this

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 3

JaredPar: oldKeys, currKeys. , A currKeys, oldKeys, diff.

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

.

Answer 4

Two bit fields, run binary XOR. No matter who you are with, you want to.