Entfernen Sie Duplikate aus generische Liste

Question

Ich habe kam mit Lösung Duplikate von generischer Liste zu entfernen in .NET 2.0 wie folgt:

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

Meine Fragen sind:

Gibt es eine effizientere Art und Weise, dies zu tun? Nur .NET 2.0-Lösung
Was ist die Komplexität der obigen Lösung?

Danke,
jan2k10

Answer 1

Die Zeitkomplexität von RemoveAll ist O (n). Die Zeitkomplexität des Indexierungs ist O (n), so dass das, eine Gesamtsumme von O (n ^ 2) Zeitkomplexität. Die Speicherkomplexität ist, glaube ich, O (1).

Gibt es eine effizientere Art und Weise, es zu tun? Ja. Sie tun können, es in O (n) Zeit Komplexität, vorausgesetzt, Sie sind bereit, auf sie mehr Platz zu verbringen.

Answer 2

Just auf Erics Kommentar zu O (n) Zeit zu erweitern, wenn Sie glücklich mehr Raum zu bedienen, ich etwas tun würde, wie folgt aus:

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

Ein paar Anmerkungen:

• Dadurch ändert sich der Wert von caseStudies auf eine neue Liste zu verweisen. Wenn Sie es sich im gleichen List<T> wollen, könnten Sie verwenden:

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

• Dies hält den letzten -Element in der Liste mit jedem deutlichen Str Wert. Das war nur, um es so kurz wie möglich zu machen. Wenn Sie die zuerst -Element, zu verwenden:

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