如何找到一个超集，它不是一个子项

Question

我知道有一个“不”的IEnumerable感谢到LINQ，这需要收集到不反对，但我很担心大哦性能什么是最快的算法来做到这一点？

Answer 1

以从IEnumerable<T>删除项目的子集的唯一方法是遍历超集和用于在通过该子集中的超环的每个项目中，如果在所述子集中找到除去从超集项目

这会给你 O（N²）平均。

现在是否有关于这些藏品（也许一个或两个是一个列表或者可能一个或两个序列进行排序），可以帮助您创建一个更高性能的解决方案的更多信息。

如果您有兴趣，这里是一个扩展方法，会做什么，我刚才所描述的：

public static IEnumerable<T> Exclude<T>
    (this IEnumerable<T> source, IEnumerable<T> items)
{
    foreach (T t in source)
        if (!items.Contains(t))
            yield return t;
}

---

没关系，使用 Enumerable.Except 扩展方法：

  

生成两个序列的差集。

Answer 2

如果可以在顺序遍历集合，可以保证为O（n）的行为（而不是“典型地为O（n），但可能是O（N²）在最坏的情况下”的是一个HashSet具有）通过迭代他们两个步调一致。

例如：

//loop boilerplate
if(itemA < itemB) {
    itemA = a.next();
    continue;
}
if(itemA > itemB) {
    itemB = b.next();
    continue;
}
a.remove(itemA);

您需要添加边界检查和其他样板自己。

Answer 3

您可以通过超集转换成散列表获得更好的性能（为O（n）典型地，但随后，可以执行在恒定的时间的查询）。然后，你可以枚举子集并检查是否超存在的每个项目。整个操作应该采取O（n）的额外的内存和O（n）的时间。