javascript - 我需要加快速度以通过代码战斗测试(javascript)

Question

任务是获取一个数组并返回最早的重复项，如果没有则返回 -1。我是这样写的:

function firstDuplicate(a) {
    let singles = [];

    for (let i = 0; i < a.length; i++) {

        if (singles.indexOf(a[i]) == -1) {
            singles.push(a[i]);
        }
        else {
            return a[i];
        }

    }

    return -1;
}

它通过了除隐藏速度测试之外的所有测试。有没有另一种方法可以在 JS 中更快地编写它？我看到一个使用集合而不是数组的 Java 解决方案，但我想坚持使用 JS。

Answer 1

您可以使用 Set在 JavaScript 中也可以实现这一点:

function firstDuplicate(array) {
  const set = new Set()

  for (const value of array) {
    if (set.has(value)) {
      return value
    }

    set.add(value)
  }

  return -1
}

console.log(firstDuplicate(['a', 1, 'b', 2, 'c', 1, 2, 3]))

您的解决方案存在问题，如 @Zabuza 所述, 是你使用的 indexOf()这会将您的算法的时间复杂度从 O(n) 更改为 O(n²)，因为每个 indexOf() 都是 O(n)。

使用 Set 而不是 Array 利用散列，它通过使用 has() 改变您的查找时间对于从 O(n) 到 O(1) 的重复，从而使算法总体上恢复到 O(n) 复杂度。