javascript - 为 codefighters javascript firstDuplicate() 函数加速此代码

Question

来自 Codefighters:

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.

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Example

For a = [2, 3, 3, 1, 5, 2], the output should be firstDuplicate(a) = 3.

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than than second occurrence of 2 does, so the answer is 3.

For a = [2, 4, 3, 5, 1], the output should be 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 = a.lastIndexOf(a[i])
        if (last > i && (low === undefined || last < low)) {
            low = last;
        }
    }

    return low !== undefined ? a[low] : -1;
}

Answer 1

需求给出了解决这个问题的线索。数组中包含的数字集必须符合以下条件:

only numbers in the range from 1 to a.length

换句话说，只有小于或等于数组长度的正数。如果数组包含十个数字，则它们都不会大于 10。

有了这种洞察力，我们就有了一种方法来跟踪我们已经看到的数字。我们可以将数字本身视为数组的索引，修改该索引处的元素(在本例中为负数)，如果我们遇到相同的数字并且该索引处的元素小于零，那么我们知道我们看过了。

console.clear()
const test1 = [2, 3, 3, 1, 5, 2]
const test2 = [2, 4, 3, 5, 1]


function firstDuplicate(a) {
  for (let i of a) {
    let posi = Math.abs(i) - 1
    if (a[posi] < 0) return posi + 1
    a[posi] = a[posi] * -1
  }

  return -1
}

console.log(firstDuplicate(test1))
console.log(firstDuplicate(test2))
console.log(firstDuplicate([2,2]))
console.log(firstDuplicate([2,3,3]))
console.log(firstDuplicate([3,3,3]))

原始错误答案

跟踪已经看到的数字并返回之前看到的第一个数字。

console.clear()
const test1 =   [2, 3, 3, 1, 5, 2]
const test2 = [2, 4, 3, 5, 1]

      
function firstDuplicate(a){
  const seen = {}
  for (let v of a){
    if (seen[v]) return v
    seen[v] = v
  }
  
  return -1
}

console.log(firstDuplicate(test1))
console.log(firstDuplicate(test2))

然而，正如评论中所指出的，这个答案需要 O(n) 的额外空间，而不是 O(1) 的额外空间。