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

Question

Я получил решение удалить дубликаты из общего списка в .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), так что это общая сложность O (n ^ 2). Я думаю, что сложность пространства равна O (1).

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

Answer 2

Просто чтобы расширить комментарий Эрика о времени, если вы будете рады использовать больше места, я бы сделал что-то вроде этого:

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. Это было просто, чтобы сделать его как можно короче. Если вам нужен элемент first , используйте:

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