如何改进我的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) (执行O(Logn)的n个搜索)。

一个更好的方法是拥有与输入范围相同大小的数组，并“勾选”您已经拥有的每个值。此搜索在固定时间内运行，但如果输入范围很大，则会变得效率低下。

Answer 2

您可以使用distinct：

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();