驗證兩個列表是否在C＃中共享值

Question

我想知道兩個列表在應用交集之前是否共享值。像布爾DoIntersect（listA，listB）將是神話般的！

這是我想出了代碼：不改變，你正在使用一個列表，你不能得到更好的性能的事實

// Person is a class with Id and Name properties 
List<Person> people1; 
List<Person> people2; 

// Populate people1 and people2... 

// My current solution (pseudocode obviously)... 

if (DoIntersect(people1, people2)) 
{ 
    people1 = people1.Intersect(people2) 
} 
else 
{ 
    /* No shared people */ 
    throw exception; 
} 

// Continue with the process... 

Answer 1

這取決於你想要什麼：

// are there any common values between a and b? 
public static bool SharesAnyValueWith<T>(this IEnumerable<T> a, IEnumerable<T> b) 
{ 
    return a.Intersect(b).Any(); 
} 

對於不重疊的名單，這將通過迭代和b各一次。對於重疊的列表，這將遍歷a，然後遍歷b，直到找到第一個重疊元素。

// does a contain all of b? (ignores duplicates) 
public static bool ContainsAllFrom<T>(this IEnumerable<T> a, IEnumerable<T> b) 
{ 
    return !b.Except(a).Any(); 
} 

這將遍歷一次，然後將迭代通過b，停止b中的第一個元素不在a中。

// does a contain all of b? (considers duplicates) 
public static bool ContainsAllFrom<T>(this IEnumerable<T> a, IEnumerable<T> b) 
{ 
    // get the count of each distinct element in a 
    var counts = a.GroupBy(t => t).ToDictionary(g => g.Key, g => g.Count()); 
    foreach (var t in b) { 
     int count; 
     // if t isn't in a or has too few occurrences return false. Otherwise, reduce 
     // the count by 1 
     if (!counts.TryGetValue(t, out count) || count == 0) { return false; } 
     counts[t] = count - 1; 
    } 

    return true; 
} 

類似地，這將通過一次迭代，然後將至b迭代，b中不處於停止在第一元件上。

Answer 2

我相信。但是，如果你有2排序列表開始於（需要開銷時），那麼你可以遍歷它們的複雜度爲O（n），以確定你是否有共享值。

編輯：

雖然原來OP沒有2排序的列表，萬一有人需要它，這裏是在O檢查交集（N）的實現：

public Boolean DoIntersect(SortedList<int,String> listA,SortedList<int,String> listB ) 
    { 
     if (listA == null || listA.Count == 0 || listB == null || listB.Count == 0) 
     { 
      return false; 
     } 
     var keysA = listA.Keys; 
     var keysB = listB.Keys; 
     int i = 0, j = 0; 
     while (i < listA.Count && j < listB.Count) 
     { 
      if (keysA[i] < keysB[j]) 
      { 
       i++; 
      }else if (keysA[i] > keysB[j]) 
      { 
       j++; 
      } 
      else 
      { 
       return true; 
      } 
     } 

上面的方法也可以用於IEnumerable列表，因爲它們是排序的，只有很小的變化 - 使用GetEnumerator並迭代它。