C# определить дубликат в списке

требование: в несортированном списке определите, существует ли дубликат. Типичный путь я хотел бы сделать это квадратичная вложенный цикл. Мне интересно, как другие решают эту. Есть ли элегантный, высокопроизводительный метод в Linq? Что-то общее, что принимает лямбда или компаратор, было бы неплохо.

11 51
c# linq list algorithm generics

11 ответов:

Если я чего-то не хватает, то вы должны быть в состоянии уйти с чем-то простым с помощью Distinct(). Конечно, это будет не самая сложная реализация, которую вы могли бы придумать, но она скажет вам, если какие-либо дубликаты будут удалены:

var list = new List<string>();

// Fill the list

if(list.Count != list.Distinct().Count())
{
     // Duplicates exist
}
110

согласно статье Эрика Уайта о том, как найти дубликаты с помощью 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
33

чтобы разрешить короткое замыкание, если дубликат существует в начале списка, вы можете добавить HashSet<T> и проверьте возвращаемое значение его .Add метод.

С помощью .Any вы можете закоротить перечисление, как только найдете дубликат.

вот метод расширения LINQ как в C#, так и в 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

14

Поместите все элементы в набор, и если количество набора отличается от количества списка, то есть дубликат.

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, так как нет необходимости проходить через весь список.

13

что-то в этом роде относительно просто и предоставит вам количество дубликатов.

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, хотя я не уверен.

2

вы можете использовать IEnumerable.GroupBy метод.

var list = new List<string> {"1", "2","3", "1", "2"};
var hasDuplicates = list.GroupBy(x => x).Any(x => x.Skip(1).Any());
2

вы можете использовать метод расширения Distinct () для IEnumerable

1

Если вы используете целые числа или хорошо упорядоченные наборы, используйте двоичное дерево для производительности O(nlog n).

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

1

использовать 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. Это не будет повторять весь список.

1

вы могли бы использовать Distinct() оператор для поиска уникальных записей. Затем сравните с оригинальным общим списком следующим образом:

  if (dgCoil.ItemsSource.Cast<BLL.Coil>().ToList().Count != dgCoil.ItemsSource.Cast<BLL.Coil>().Select(c => c.CoilNo).Distinct().Count())
  {    
    //Duplicate detected !!
    return;
  }
0

не видел, чтобы кто-нибудь это делал, поэтому вот небольшая программа, которую я только что написал. Это достаточно просто. Использование Contains (), хотя я не знаю, насколько масштабируемый этот метод.

       Console.WriteLine("Please enter 5 unique numbers....");
        List<int> uniqueNums = new List<int>() { };
        while (uniqueNums.Count < 5)
        {
            int input = Convert.ToInt32(Console.ReadLine());
            if (uniqueNums.Contains(input))
            {
                Console.WriteLine("Add a different number");
            }
            uniqueNums.Add(input);
        }
        uniqueNums.Sort();
        foreach (var n in uniqueNums)
        {
            Console.WriteLine(n);
        }
-1