Как улучшить мой FindDuplicate классический алгоритм

Question

У меня есть классический алгоритм поиска дубликатов, как это:

int n = int.Parse(Console.ReadLine()); 
      Console.WriteLine(); 
      List<int> tempArr = new List<int>(); 
      List<int> array = new List<int>(); 
      for (int i = 0; i < n; i++) 
      { 
       Console.Write("input number {0}: ", i + 1); 
       tempArr.Add(int.Parse(Console.ReadLine())); 
      } 
      tempArr.Sort(); 
      for (int i = 0; i < n; i++) 
      { 
       for (int j = i+1; j < n; j++) 
       { 
        if (tempArr[i] == tempArr[j]) 
        { 
         array.Add(tempArr[i]); 
        } 
       } 
      } 

Все работы в порядке, но если у меня есть только два дублирующие номера как (1, 2,2, 3,4,5), как я могу добавить их как в List<int> **array** с одним чистым снимком в петле?

Answer 1

Вместо списков вы могли бы использовать какой-то структуры данных, которые имеют лучшую возможность поиска (хэш-таблицы или бинарных деревьев, для пример). Даже если у вас есть только один дубликат, проблема в том, что вам нужно проверить, добавлен ли вы в этот элемент в списке, поэтому ключевая операция в вашем алгоритме - это поиск. Чем быстрее вы выполняете поиск, тем быстрее будет алгоритм. Используя бинарный поиск, который является самым быстрым способом поиска, вы получаете O (nlogn) (вы выполняете n поисков O (logn)).

Даже лучший способ сделать это - иметь какой-то массив, который имеет тот же размер, что и ваш диапазон ввода, и «галочка» каждого значения, которое у вас уже есть. Этот поиск выполняется в постоянное время, но становится неэффективным, если у вас большой диапазон ввода.

Answer 2

Вы можете использовать отчетливый:

array = tempArr.Distinct().ToList(); 

Distinct не в линейном времени, если это то, что вы ищете («один чистый выстрел»). Если вы знаете больше о вводе, вы можете найти способ сделать это в линейном времени. Например, если вы знаете, находятся ли целые числа в определенном диапазоне.

Answer 3

Чтобы экстракт все дубликаты, которые вы можете использовать Linq:

List<int> tempList = new List<int>() { 1, 2, 2, 3, 4, 5 }; 

    // array == [2, 2] 
    List<int> array = tempList 
    .GroupBy(x => x) 
    .Where(x => x.Count() > 1) 
    .SelectMany(x => Enumerable.Repeat(x.Key, x.Count())) 
    .ToList();