从通用列表<T>中删除重复项

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;
      }
  }