验证两个列表是否在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并迭代它。