小编rie*_*rsn的帖子

每个Codefighters:

注意:编写具有O(n)时间复杂度和O(1)额外空间复杂度的解决方案,因为这是您在真实访谈期间要求做的事情.

给定一个仅包含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.

所以这就是我想出来的.它工作但最终测试失败,因为它运行超过4000毫秒.我不知道我还能做些什么.有什么提高速度的想法吗？

function firstDuplicate(a) {
    var test   = [],
        lowest = undefined;

    for (var i=0; i<a.length; i++) {
        if (test.indexOf(a[i]) > -1) {
            lowest = lowest || i;
            if (i < lowest) {
                lowest = i;
            }
        }
        else {
            test.push(a[i]);
        }
    }

    return lowest ? a[lowest] : -1;
}

这是我的第二次尝试,但在最后一次测试中仍未通过......

function firstDuplicate(a) {
    var low = undefined,
        last = -1;

    for (var i=0; i<a.length; i++) {
        last …