求两个数组之差的算法
求两个数组之差的算法
提问于 2009-02-19 18:23:13
给定两个数组，有没有一种快速算法可以找到这两个数组中所有不同的元素？例如，考虑两个键(如键盘键)结构的数组。一个表示当前按下的键，另一个表示上一时间步中按下的键。
Keys[] oldKeys = LastKeyboardState.GetPressedKeys();
Keys[] currKeys = CurrentKeyboardState.GetPressedKeys();
// the user just pressed these key(s) during the last timestep.
Keys[] diff = ...非常感谢您的建议！
回答 4
Stack Overflow用户
回答已采纳
发布于 2009-02-19 18:26:17
尝尝这个
var diff = oldKeys.Except(currKeys);这需要C# 3.0
Stack Overflow用户
发布于 2009-02-19 18:36:25
暴力算法应该是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);
}
}Stack Overflow用户
发布于 2009-02-19 18:35:44
在JaredPar上跟进:这将只在oldKeys中显示密钥，而不会在currKeys中显示。因此，如果A在currKeys中但不在oldKeys中，它将不会出现在diff中。
差异变量oldKeys.Union(currKeys).Except(currKeys.Intersect(oldKeys)) =
也会得到这些。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/566539
复制相关文章
相似问题
腾讯云开发者
