Javascript 中关于 CodeSignal 的第一个重复问题

Question

我不明白为什么我在这个挑战中通过了 22/23 而无法解决最后一个测试用例，因为它被隐藏了。CodeSignal 的反馈是

Tests passed: 22/23. Execution time limit exceeded: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input.

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

例子

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

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

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

Input/Output

[执行时限]4秒(js)

[输入]array.integer一个

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

[输出]整数

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

我的代码

function solution(a) {
  let first = Infinity
  for ( let i = 0; i<a.length; i++ ) {
      let pointer = i+1;
      while (pointer <a.length) {
          if (a[i] === a[pointer] && pointer<first) {
              first = pointer;
          } 
          pointer +=1
      }
  } 
  if (first === Infinity) {
      return -1
  }
  return a[first]
}

谢谢。

Answer 1

在糟糕的情况下，您要为其中的每个元素遍历整个数组 - O(n ^ 2)。内部 while(pointer < a.length) 导致参数花费太多时间。

相反，创建一组到目前为止找到的元素，并在找到第一个重复元素（这将是最小的第二个索引）时 return。

const solution = (a) => {
  const set = new Set();
  for (const item of arr) {
    if (set.has(item)) return item;
    set.add(item);
  }
  return -1;
};

因为没有嵌套循环（.has 和 .add 是 O(1)），所以总体上是 O(n)，应该足够快了。

Javascript 中关于 CodeSignal 的第一个重复问题

firstDuplicate question on CodeSignal in Javascript

javascript

algorithm

testcase