如何在C#中对数组执行集合减法？

Question

在C#中，给定两个数组，执行集合减法的最简单方法是什么？显然，在Ruby中这很容易。基本上，我只想从数组a中删除数组b中存在的元素：

string[] a = new string[] { "one", "two", "three", "four" };
string[] b = new string[] { "two", "four", "six" };
string[] c = a - b; // not valid

c 应该等于 { "one", "three" }。 b - a 将产生 { "six" }。

- devios1

Answer 1

如果你正在使用 Linq，你可以像这样使用 Except 操作符：

string [] c = a.Except(b).ToArray();

编辑: CodeInChaos提出了一个很好的观点。如果a包含重复项，它也将删除所有重复项。要使其与Ruby版本完全相同，可使用以下代码：

string [] c = a.Where(x=>!b.Contains(x)).ToArray();

- Keltex

---

请注意，这将仅返回唯一的元素。因此，如果您在a中有一个元素出现两次，它只会保留第一个。 - CodesInChaos

太棒了，谢谢——不知道我怎么会错过那个。可能是命名把我搞糊涂了。 - devios1

替代方案将会移除重复项！ - xanatos

@Keltez，你的替代方法仍然会删除重复项。如果你有 { 'A', 'A' } - {'A'} == { } - xanatos

@xanatos - 这是正确的行为，即从A中删除所有在B中的元素。另一方面，我的替代方法将得到 {'B','B'} - {'A'} = {'B','B'}。 - Keltex

Answer 2

public static IEnumerable<T> Minus<T>(this IEnumerable<T> enum1, IEnumerable<T> enum2)
{
    Dictionary<T, int> elements = new Dictionary<T, int>();

    foreach (var el in enum2)
    {
        int num = 0;
        elements.TryGetValue(el, out num);
        elements[el] = num + 1;
    }

    foreach (var el in enum1)
    {
        int num = 0;
        if (elements.TryGetValue(el, out num) && num > 0)
        {
            elements[el] = num - 1;
        }
        else
        {
            yield return el;
        }
    }
}

这不会从enum1中删除重复项。明确一下：

1. { 'A', 'A' } - { 'A' } == { 'A' }
2. { 'A', 'A' } - { 'A' } == { }

我执行第一个，Enumerable.Except执行第二个。

- xanatos

---

应该将 elements.Remove 改为 elements.Contains。 - Keltex

@Keltex，这个想法是要将它删除，因为它已经被计算过了。然而，我认为它应该是一个List而不是一个HashSet，因为否则它不能考虑到 {a, a, a} - {a, a} = {a}。 - devios1

不，它应该是一个字典，因此我仍然处于O（m * log（n））（从技术上讲可能是O（（m + 1）* log（n）））的时间复杂度。 - xanatos

使用Linq，您只需执行var elements = enum2.GroupBy(el => el).ToDictionary(elg => elg.Key, elg => elg.Count());。 - NetMage