在int数组中重复值(最佳性能)

本文关键字：最佳 性能 int 数组 | 更新日期: 2023-09-27 18:03:42

我有一个数字数组，其中有一些重复的值。我想找出前两个重复的数字。

真正的问题是它必须在最佳性能，我不能使用LINQ，它必须在经典代码。

真正的问题是关于最佳性能，所以它意味着最佳答案是最快的语言和最快的算法。

我在c#中尝试过:

        int[] numbers = {5, 2, 10, 18, 55, 100, 10, 50, 23, 6, 14, 25, 12};
        int result1 = -1;
        int result2 = -1;
        for (int i = 0; i < numbers.Length; i++)
        {
            for (int j = 0; j < numbers.Length; j++)
            {
                if (numbers[j] == numbers[i] & i != j)
                {
                    result2 = j;
                    result1 = i;
                    J = numbers.Length;  //this will cause loop exit.
                    i = numbers.Length;  //this will cause first loop to exit.
                }
            }
        }
        Console.Write("The result of search is {0} and {1}", result1, result2);
        Console.ReadLine();

在int数组中重复值(最佳性能)

使用字典来存储数字和找到它们的位置，当您找到字典中存在的数字时，您就拥有了副本及其位置。在字典中添加和定位项是O(1)个操作，因此该算法是O(n)个操作:

int[] numbers = { 5, 2, 10, 18, 55, 100, 10, 50, 23, 6, 14, 25, 12 };
Dictionary<int, int> found = new Dictionary<int,int>();
int result1 = -1, result2 = -1;
for (int i = 0; i < numbers.Length; i++) {
  int number = numbers[i];
  int pos;
  if (found.TryGetValue(number, out pos)) {
    result1 = pos;
    result2 = i;
    break;
  }
  found.Add(number, i);
}
Console.Write("The result of search is {0} and {1}", result1, result2);
Console.ReadLine();

为了获得一些额外的性能，您可以为字典中可能需要的所有项预先分配空间。这在平均情况下使用更多的内存，但可以防止字典在增长时重复分配更多的空间:

Dictionary<int, int> found = new Dictionary<int,int>(numbers.Length);
相关文章：