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

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）時間。

Answer 3

如果你能以遍歷集合，可以保證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); 

你需要添加邊界檢查和其他樣板自己。