如何在C#中高效查找数组中的第一个重复数字？

我正在学习C#，需要解决查找数组中第一个重复数字的问题。例如，数组{ 1, 2, 3, 4, 2, 5 }的答案应为2，因为它是第一个重复出现的数字。

当前实现方法 #

以下是我当前的实现：

int[] numbers = { 1, 2, 3, 4, 2, 5 };
int duplicate = -1;

for (int i = 0; i < numbers.Length; i++)
{
    for (int j = i + 1; j < numbers.Length; j++)
    {
        if (numbers[i] == numbers[j])
        {
            duplicate = numbers[i];
            break;
        }
    }
    if (duplicate != -1) break;
}

Console.WriteLine(duplicate);

该方法可行，但采用嵌套循环，时间复杂度为O(n²)，处理较大数组时速度较慢。

基于HashSet的优化方案 #

可以利用HashSet<T>来优化，它的查找和插入操作平均时间复杂度为O(1)，能将整体时间复杂度降到O(n)。核心思路是：遍历数组时，用HashSet记录已遍历过的元素，遇到第一个无法加入HashSet的元素，就是第一个重复的数字。

实现代码 #

using System.Collections.Generic;

int[] numbers = { 1, 2, 3, 4, 2, 5 };
int duplicate = -1;
HashSet<int> seenNumbers = new HashSet<int>();

foreach (int num in numbers)
{
    if (!seenNumbers.Add(num))
    {
        duplicate = num;
        break;
    }
}

Console.WriteLine(duplicate);

逻辑说明 #

• HashSet<int>.Add()方法会尝试将元素加入集合：如果元素不存在，添加成功并返回true；如果元素已存在，添加失败并返回false。
• 遍历数组时，每遇到一个元素就调用Add方法，一旦返回false，说明这个元素是之前已经出现过的，也就是第一个重复的元素，直接记录并跳出循环即可。
• 如果遍历完整个数组都没有找到重复元素，duplicate保持初始值-1。

内容的提问来源于stack exchange，提问作者Harsh Parmar