C#改进算法

Question

我在面试(C#3.0)中被要求提供一个逻辑来从列表中删除项目列表.

我回答了

int[] items={1,2,3,4}; 
List<int> newList = new List<int>() { 1, 2, 3, 4, 5, 56, 788, 9 };
newList.RemoveAll((int i) => { return items.Contains(i); });

1)面试官回答说,我采用的算法会逐渐花费时间,如果项目增长,并要求我提供更好,更快的算法.什么是有效的算法？

2)如何使用LINQ实现相同的目标？

3)他让我提供一个双向关闭的例子？(一般我知道关闭,什么是双向关闭？,我回答说没有这样的术语存在,但他并不满足).

Answer 1

编辑更好的解决方案:使用Except不对称的,不像Intersect.

1和2:您可以使用Intersect扩展方法执行此操作.但是,如果您的第二个数组包含在第一个数组中找不到的元素,则这些元素将位于结果列表中:Intersect对称地工作.

至于"双向关闭",我从未听说过这个术语,我更怀疑它是一个既定的技术术语.

Answer 2

你的答案是O(N ^ 2),因为你必须在小列表中搜索大列表中的每个元素.你可能有运气使用哈希表或带二进制搜索的排序列表(在整数/字符串的情况下),以及其他各种方法来减少查找开销,这至少会让你到O(N日志) N).

值得注意的是,如果小列表的大小与大列表的大小不相似,那么您的解决方案是O(N*M); 您可能希望首先优化通常较大的列表.如果您可以对第一个列表进行排序,那么这是一个不错的选择; 如果不允许修改它,请不要忘记对第二个列表进行排序/哈希.

Answer 3

使用Except的示例

var exclusions = new List<int>() { 1, 2, 3, 4 };
var newList = new List<int>() { 1, 2, 3, 4, 5, 56, 788, 9 };
IEnumerable<int>result = newList.Except(exclusions);