arrays - 找出两个数组之间差异的算法

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

好吧，蛮力算法将是 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);
    }
}