Требование: в несортированном списке определить, существует ли дубликат. Типичным способом я сделаю это n-квадрат вложенного цикла. Мне интересно, как другие решают это. Есть ли элегантный, высокопроизводительный метод в Linq? Что-то общее, что принимает лямбда или компаратор, было бы неплохо.
С# Определить дубликат в списке
Ответ 1
Если я чего-то не упускаю, вы можете уйти с чем-то простым, используя Distinct()
. Конечно, это не будет самая сложная реализация, которую вы могли бы придумать, но она скажет вам, удалены ли дубликаты:
var list = new List<string>();
// Fill the list
if(list.Count != list.Distinct().Count())
{
// Duplicates exist
}
Ответ 2
Согласно статье Эрика Уайта о том, как Найти дубликаты с помощью LINQ:
Простым способом поиска дубликатов является запись запроса, который группируется по идентификатору, а затем фильтра для групп, которые имеют более одного члена. В следующем примере мы хотим знать, что 4 и 3 являются дубликатами:
int[] listOfItems = new[] { 4, 2, 3, 1, 6, 4, 3 }; var duplicates = listOfItems .GroupBy(i => i) .Where(g => g.Count() > 1) .Select(g => g.Key); foreach (var d in duplicates) Console.WriteLine(d); // 4,3
Ответ 3
Поместите все элементы в набор, и если счетчик набора отличается от количества списков, тогда существует дубликат.
bool hasDuplicates<T>(List<T> myList) {
var hs = new HashSet<T>();
for (var i = 0; i < myList.Count; ++i) {
if (!hs.Add(myList[i])) return true;
}
return false;
}
Должен быть более эффективным, чем Distinct, поскольку нет необходимости проходить через весь список.
Ответ 4
Чтобы обеспечить короткое замыкание, если дубликат существует в начале списка, вы можете добавить HashSet<T>
и проверить возвращаемое значение его метода .Add
,
Используя .Any
, вы можете коротко закодировать перечисление, как только найдете дубликат.
Здесь метод расширения LINQ как в С#, так и в VB:
Csharp:
public static bool ContainsDuplicates<T>(this IEnumerable<T> enumerable)
{
var knownKeys = new HashSet<T>();
return enumerable.Any(item => !knownKeys.Add(item));
}
Visual Basic:
<Extension>
Public Function ContainsDuplicates(Of T)(ByVal enumerable As IEnumerable(Of T)) As Boolean
Dim knownKeys As New HashSet(Of T)
Return enumerable.Any(Function(item) Not knownKeys.Add(item))
End Function
Примечание: чтобы проверить, нет ли дубликатов, просто измените Any
на All
Ответ 5
Что-то в этих строках относительно просто и предоставит вам количество дубликатов.
var something = new List<string>() { "One", "One", "Two", "Three" };
var dictionary = new Dictionary<string, int>();
something.ForEach(s =>
{
if (dictionary.ContainsKey(s))
{
dictionary[s]++;
}
else
{
dictionary[s] = 1;
}
});
Я предполагаю, что это похоже на реализацию Distinct, хотя я не уверен.
Ответ 6
Вы можете использовать метод расширения Distinct() для IEnumerable
Ответ 7
Если вы используете целые числа или упорядоченные наборы, используйте двоичное дерево для производительности O (nlog n).
В качестве альтернативы найдите еще одно более быстрое средство сортировки, а затем просто проверьте, что каждое значение отличается от предыдущего.
Ответ 8
Используйте Enumerable.Any
с помощью HashSet.Add
как:
List<string> list = new List<string> {"A", "A", "B", "C", "D"};
HashSet<string> hashSet = new HashSet<string>();
if(list.Any(r => !hashSet.Add(r)))
{
//duplicate exists.
}
HashSet.Add
вернет false
, если элемент уже существует в HashSet
. Это не приведет к перебору всего списка.
Ответ 9
Вы можете использовать метод IEnumerable.GroupBy.
var list = new List<string> {"1", "2","3", "1", "2"};
var hasDuplicates = list.GroupBy(x => x).Any(x => x.Skip(1).Any());