java - CodeFights - 编写 FirstDuplicate 方法时的时间限制问题

Question

我正在尝试从 CodeFights 解决以下问题。问题结束后，我用 Java 留下了答案。该代码适用于除最后一个问题之外的所有问题。报时限异常。我该怎么做才能让它运行在 3000 毫秒以下(CodeFights 要求)？

Note: Write a solution with O(n) time complexity and O(1) additional space complexity, since this is what you would be asked to do during a real interview.

给定一个仅包含 1 到 a.length 范围内数字的数组 a，找到第一个重复数字，其中第二次出现的数字具有最小索引。换句话说，如果有超过 1 个重复的数字，则返回第二次出现的索引小于另一个数字的第二次出现的索引的数字。如果没有这样的元素，返回-1。

例子

对于 a = [2, 3, 3, 1, 5, 2]，输出应该是firstDuplicate(a) = 3.

有 2 个重复项:数字 2 和 3。第二次出现的 3 的索引小于第二次出现的 2 的索引，所以答案是 3。

对于 a = [2, 4, 3, 5, 1]，输出应该是firstDuplicate(a) = -1.

输入/输出

[时间限制] 3000ms (java)[输入] array.integer a

保证约束:1 ≤ a.length ≤ 105,1 ≤ a[i] ≤ a.length.

[输出]整数

a 中的元素在数组中出现不止一次，并且在第二次出现时具有最小索引。如果没有这样的元素，返回-1。

    int storedLeastValue = -1;
    int indexDistances = Integer.MAX_VALUE;
    int indexPosition = Integer.MAX_VALUE;

    for (int i = 0; i < a.length; i++) 
    {   
            int tempValue = a[i];

            for (int j = i+1; j < a.length; j++) {
                if(tempValue == a[j])
                {
                    if(Math.abs(i-j) < indexDistances && 
                      j < indexPosition)
                    {
                        storedLeastValue = tempValue;
                        indexDistances = Math.abs(i-j);
                        indexPosition = j;
                        break;
                    }
                }
            }
        }

        return storedLeastValue;

Answer 1

您的解决方案有两个嵌套的 for 循环，这意味着 O(n^2) 而问题明确要求 O(n)。由于您也有空间限制，因此您不能使用额外的 Set (它也可以提供一个简单的解决方案)。

这个问题适合有很强算法/图论背景的人。该解决方案非常复杂，包括在有向图中找到循环的入口点。如果您不熟悉这些术语，我建议您离开并转到其他问题。