3

我想知道在应用交集之前两个列表是否共享值。像bool 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...
4

2 回答 2

4

这完全取决于您想要什么：

// 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();
}

对于不重叠的列表，这将遍历 a 和 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();
}

这将遍历 a 一次，然后将遍历 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;
}

类似地，这将遍历 a 一次，然后将遍历 b，在 b 中的第一个元素上停止，而不是在 a 中。

于 2013-07-06T20:36:09.693 回答
1

我相信如果不改变您使用 List 的事实，您将无法获得更好的性能。

但是，如果您将有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 并对其进行迭代。

于 2013-07-06T20:34:29.773 回答