C#从另一个列表中减去一个列表或检查一个列表是否完全包含在另一个列表中

Question

如何从另一个列表中减去一个列表？

  List<string> l1 = new List<string> { "abc", "abc", "abc", "def" };
  List<string> l2 = new List<string> { "abc" };
  var r = l1.Except(l2).ToList();

这样做会导致r =>"def"而不是r =>"abc","abc","def".我的意思是,第二个列表只包含一次"abc".所以我想只删除第一个列表的"abc"的一个实例.

顺便说一句:有没有办法检查一个列表是否完全包含在另一个列表中？当list1仅包含"abc"一次而list2包含"abc"两次时,list2不包含在list1中.Except不适用于多个值.

Answer 1

您可以编写自己的扩展方法MyExcept

public static IEnumerable<T> MyExcept<T>(this IEnumerable<T> orgList, IEnumerable<T> toRemove)
{
    var list = orgList.ToList();
    foreach(var x in toRemove)
    {
        list.Remove(x);
    }
    return list;
}

根据Alexei Levenkov评论,有一点改进......

public static IEnumerable<T> MyExcept2<T>(this IEnumerable<T> orgList, IEnumerable<T> toRemove)
{
    var list = orgList.OrderBy(x => x).ToList();
    foreach (var x in toRemove)
    {
        var inx = list.BinarySearch(x);
        if (inx >= 0) list.RemoveAt(inx);
    }
    return list;
}

Answer 2

Except不起作用，因为它将其操作数视为集合。

解决此问题的一种方法是创建计数，减去它们，然后重新创建列表：

// Make word counts for l1 and l2
var c1 = l1.GroupBy(x => x).ToDictionary(g => g.Key, g => g.Count());
var c2 = l2.GroupBy(x => x).ToDictionary(g => g.Key, g => g.Count());
// Make a count of the difference between the two
var diff = new Dictionary<string,int>();
foreach (var p in c1) {
    int sub;
    if (!c2.TryGetValue(p.Key, out sub)) {
        sub = 0;
    }
    diff[p.Key] = p.Value - sub;
}
// Reconstruct the result from counts
var res = diff.SelectMany(p => Enumerable.Repeat(p.Key, p.Value)).ToList();

这个算法是O(M+N)

演示。