找到两个数组之间差异的算法

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