Supprimer les doublons de la liste générique <T>

Question

Je suis venu avec une solution pour supprimer les doublons de la liste générique <T> dans .NET 2.0 comme suit:

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

Mes questions sont les suivantes:

Y at-il moyen plus efficace pour faire ça? Seule la solution .NET 2.0
Quelle est la complexité de la solution ci-dessus?

Merci,
jan2k10

Answer 1

La complexité temporelle de RemoveAll est O (n). La complexité temporelle de l'indexation est O (n), donc c'est un total général de complexité de temps O (n^2). La complexité de l'espace est, je pense, O (1).

Existe-t-il un moyen plus efficace de le faire? Oui. Vous pouvez le faire en complexité de temps O (n) à condition que vous soyez prêt à y consacrer plus d'espace.

Answer 2

Juste pour développer le commentaire d'Eric à propos de O (n) si vous êtes heureux d'utiliser plus d'espace, je ferais quelque chose comme ceci:

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

Quelques notes:

• Ceci modifie la valeur de caseStudies pour faire référence à une nouvelle liste. Si vous vouliez qu'il soit dans le même List<T>, vous pouvez utiliser:

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

• Cela permet de maintenir le dernier élément dans la liste à chaque valeur Str distincte. C'était juste pour le rendre le plus court possible. Si vous voulez que le premier élément , utilisez:

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