查找首个重复元素的时间复杂度优化问题

嘿，我完全懂你的困扰——当数组规模达到10^5时，常规的O(n²)双重循环肯定会超时，哪怕是用HashSet的O(n)空间解法也不是最优的。好在题目给了1 ≤ a[i] ≤ a.length这个关键约束，我们可以利用它实现O(n)时间复杂度 + O(1)空间复杂度的最优解法！

原方法的问题分析 #

你的原代码（看起来是双重循环思路）时间复杂度是O(n²)，对于10^{5长度的数组来说，总操作次数会达到10}10级别，这远远超出了程序能承受的时间上限，必然会超时。

最优解法思路 #

既然元素值的范围刚好等于数组的索引范围（注意数组索引从0开始，元素从1开始），我们可以把数组本身当作哈希表来使用：

• 遍历数组中的每个元素num，计算它对应的索引位：index = Math.Abs(num) - 1（取绝对值是因为我们会把已访问过的位置标记为负数）
• 如果a[index]已经是负数，说明这个num之前已经出现过，它就是我们要找的第一个重复元素
• 如果a[index]是正数，就把它变成负数，标记为已访问过
• 如果遍历完整个数组都没找到重复元素，返回-1

C# 代码实现 #

class Program {
    static void Main(string[] args) {
        int[] a = { 2, 1, 3, 5, 3, 2 };
        int f = FirstDuplicate(a);
        Console.WriteLine(f); // 输出3，因为3是第一个重复出现的元素
        Console.ReadLine();
    }

    public static int FirstDuplicate(int[] a) {
        for (int i = 0; i < a.Length; i++) {
            int index = Math.Abs(a[i]) - 1;
            // 如果对应索引的数已经是负数，说明当前元素是重复的
            if (a[index] < 0) {
                return Math.Abs(a[i]);
            }
            // 标记为已访问：把对应索引的数转为负数
            a[index] = -a[index];
        }
        // 没有重复元素返回-1
        return -1;
    }
}

为什么这个方法高效？ #

• 时间复杂度O(n)：每个元素只被遍历一次，每次操作都是O(1)的简单计算
• 空间复杂度O(1)：完全不需要额外的哈希表或数组，只用原数组的空间
• 正确性保证：因为我们按顺序遍历，第一个遇到的已标记位置对应的元素，就是最早出现的重复元素；元素值的范围约束保证了索引不会越界

其他可选方案（空间换时间） #

如果你不想修改原数组，可以用HashSet<int>来实现O(n)时间、O(n)空间的解法，虽然空间不如上面的方法优，但代码更直观：

public static int FirstDuplicate(int[] a) {
    HashSet<int> seen = new HashSet<int>();
    foreach (int num in a) {
        if (seen.Contains(num)) {
            return num;
        }
        seen.Add(num);
    }
    return -1;
}

不过对于10^5的数组，这个方法的空间开销大约是几百KB，其实也在可接受范围内，但原地修改的方法显然更优。

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