javascript - 在大量数字中搜索第一个重复元素

Question

尝试解决这个问题 - 给定一个a仅包含从 1 到 范围内的数字的数组a.length，找到第二次出现的具有最小索引的第一个重复数字。

这是我的解决方案 -

function firstDuplicate(a) {
  for (let i = 0; i < a.length; i++) {
    if (a.indexOf(a[i]) !== i) {
      return a[i];
    }
  }

  return -1;
}

问题 - 接受标准之一是，算法应该在 4 秒内找到第一个重复值，当输入数组很大时我无法实现。我使用包含 100k 个项目的输入数组进行了测试，我的算法花费了 5 秒以上。有人可以帮我调整我的代码，让它在 4 秒内完成吗？

非常感谢！

标签： javascriptarraysalgorithm

Answer 1

您必须遍历该数组并将元素收集到临时对象，该对象将数字（元素）作为键，将一些布尔值作为索引。

在每次迭代中检查临时对象是否具有该键。

const bigArray = [];


for(let i = 0; i<1000000; i++) {
  bigArray.push(i);
}


for(let i = 0; i<1000000; i++) {
  bigArray.push(parseInt(Math.random()*1000000));
}


const firstDuplicateInArray = array => {
  const temp = {};
  for (let i = 0; i < array.length; i++) {
    if (temp[array[i]] === true) {
      return array[i];
    }
    temp[array[i]] = true;
  }
  return -1;
};

const start = new Date().getTime();
console.log('Time start:', start);

console.log('Found 1st duplicate:', firstDuplicateInArray(bigArray));

const end = new Date().getTime();
console.log('Time end:', end);

console.log('Time taken:', end - start, 'microseconds');

PSSet慢 2 倍以上（取决于数组的大小）：

const bigArray = [];


for(let i = 0; i<1000000; i++) {
  bigArray.push(i);
}


for(let i = 0; i<1000000; i++) {
  bigArray.push(parseInt(Math.random()*1000000));
}


function firstDuplicate(a) {
  const r = new Set();
  for (let e of a) {
    if (r.has(e)) return e;
    else r.add(e);
  }
  return -1;
}

const start = new Date().getTime();
console.log('Time start:', start);

console.log('Found 1st duplicate:', firstDuplicate(bigArray));

const end = new Date().getTime();
console.log('Time end:', end);

console.log('Time taken:', end - start, 'microseconds');