Какой самый эффективный способ проверить, есть ли в массиве строк дубликаты в .NET?

Question

У меня есть очень, очень большой массив несортированных строк, и мне нужно проверить, есть ли дубликаты.

Какой самый эффективный метод проверки этого?

Answer 1

Самый простой способ , вероятно:

if (strings.Length != strings.Distinct().Count())
{
    // There are duplicates
}

Это будет O (n) - но он не скажет , какие элементы были продублированы.

В качестве альтернативы:

HashSet<string> values = new HashSet<string>();
foreach (string x in strings)
{
    if (!values.Add(x))
    {
        // x was a duplicate
    }
}

Опять же, это должно быть амортизировано O (n).

Обратите внимание, что вы можете указать другой IEqualityComparer<string>, если вы хотите регистрнечувствительное сравнение или что-то в этом роде.

Answer 2

Прокрутите список и поместите каждый элемент в отсортированное дерево.Таким образом, вы можете заранее определить, есть ли дубликат.