Удалить дубликаты из списка общего <T>

Question

Я пришел с раствором для удаления дубликатов из списка общего <T> в .NET 2.0 следующим образом:

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^2). Сложность пространства, я думаю, O (1).

Есть ли более эффективный способ сделать это? Да. Вы можете сделать это в O (n) сложности времени, если вы готовы потратить больше места на нем.

Answer 2

Просто расширить на комментарии Эрика о 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; 
      } 
  }