4

我有一个可能包含重复项的无序枚举，我想删除所有具有重复项的项，并仅保留在原始枚举中仅出现一次的项。

示例：A 和 C 被删除，因为它们不止一次出现：

输入 {A,C,B,A,C,D,A}
输出 {B,D}

一个快速而肮脏的实现可能是：

IEnumerable<T> Filter(IEnumerable<T> items)
{
   items.Where(item => items.Count(x => x.Equals(item)) == 1);
}

显然不是快速或优雅。

下面的示例仍然是二次的（稍微快一点），但需要对输入进行 ToList() 调用。

IEnumerable<T> Filter(IEnumerable<T> items)
{
    List<T> src = items.ToList();
    for(int i=0; i<src.Count; i++)
    {
       if (src.IndexOf(src[i], i+1) < 0)
         yield return src[i]; 
    }
}

如果您希望它相当紧凑和可读（代码方面），同时又不会像这些实现那样慢得让人脑筋急转弯，您将如何做到这一点？

4

3 回答 3

6

LINQ 使这很容易GroupBy：

IEnumerable<String> foo = new[]{ "A", "C", "B", "A", "C", "D", "A" };
Ienumerable<String> result = foo.GroupBy (x => x)          // A=>3,C=>2,B=>1,D=>1
                               .Where(x => x.Count() == 1) // B=>1,D=>1
                               .Select (x => x.Key);       // B,D
  1. 按值分组
  2. 过滤掉只有 1 个条目的
  3. 选择原始值

不确定性能需要什么，但我倾向于发现 GroupBys 自己可读。

于 2013-04-07T18:55:27.830 回答
1

你可以及时做到这一点O(N)。

算法：

  • 创建字典 [T, count] - ( O(1) )
  • 扫描输入 - ( O(N) )，插入一个项目 - (O(1))或增加计数 - (O(1))
  • 扫描字典中计数为 1 的项目 - ( O(N) )

此解决方案需要两次完整扫描：一次是输入，第二次是结果字典。虽然，它不是 LINQ，但实际上可能比 LINQ 工作得更快。

class Program
{
    static void Main(string[] args)
    {
        var input = new[] { "A", "C", "B", "A", "C", "D", "A" };
        var result = Filter(input);
        Console.WriteLine(result);
    }

    static IEnumerable<T> Filter<T>(IEnumerable<T> items)
    {
        var dictionary = new Dictionary<T, int>();

        //first scan of the input
        foreach (T item in items)
        {
            if (dictionary.ContainsKey(item))
            {
                dictionary[item]++;
            }
            else
            {
                dictionary[item] = 1;
            }
        }

        //second scan
        return from x in dictionary
                where x.Value == 1
                select x.Key;
    }
}
于 2013-04-07T19:08:11.010 回答
0

使用集合怎么样：

IEqualityComparer<T> comparer = EqualityComparer<T>.Default;

HashSet<T> itemsToKeep = new HashSet<T>(comparer );
HashSet<T> itemsToRemove = new HashSet<T>(comparer );

foreach(T item in items)
{
   if (itemsToRemove.Add(item))
   {
       continue;
   }
   itemsToKeep.Add(item);
}

itemsToKeep.ExceptWith(itemsToRemove);

如果可能，您可以使用自定义IEqualityComparer<T>实现来加快集合的性能。

于 2013-04-07T18:56:06.240 回答