c# - 从通用列表中删除重复项

Question

我提供了从 .NET 2.0 中的通用列表<T> 中删除重复项的解决方案，如下所示：

List<CaseStudy> caseStudies = CaseStudyDAO.FindCaseStudiesByDate(DateTime.Now.Date, DateTime.Now.Date.AddDays(1));
caseStudies.RemoveAll(
        delegate(CaseStudy c)
        {
            return caseStudies.IndexOf(c) != caseStudies.FindIndex(
                delegate(CaseStudy f) { return c.Str == f.Str; });
        });

我的问题是：

有没有更有效的方法来做到这一点？只有 .NET 2.0 的解决方案
上述解决方案的复杂性是什么？

谢谢，
jan2k10

Answer 1

RemoveAll 的时间复杂度为 O(n)。索引的时间复杂度是 O(n)，所以这是 O(n^2) 时间复杂度的总和。我认为空间复杂度是 O(1)。

有没有更有效的方法来做到这一点？是的。如果您愿意在上面花费更多空间，则可以在 O(n) 时间复杂度内完成。

Answer 2

如果您愿意使用更多空间，只是为了扩展 Eric 关于 O(n) 时间的评论，我会做这样的事情：

Dictionary<string, CaseStudy> lookup = new Dictionary<string, CaseStudy>();
foreach (CaseStudy cs in caseStudies)
{
    lookup[cs.Str] = cs;
}
caseStudies = new List<CaseStudy>(lookup.Values);

几点注意事项：

• 这会将 的值更改caseStudies为引用新列表。如果您希望它在同一范围内List<T>，您可以使用：

  caseStudies.Clear();
  caseStudies.AddRange(lookup.Values);
  

• 这使列表中的最后一个元素与每个不同的Str值保持一致。那只是为了让它尽可能短。如果您想要第一个元素，请使用：

  foreach (CaseStudy cs in caseStudies)
  {
      if (!lookup.ContainsKey(cs.Str))
      {
          lookup[cs.Str] = cs;
      }
  }