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

Question

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

这是我的解决方案-

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 秒内完成吗？

非常感谢!

Answer 1

您必须遍历该数组并将元素收集到将数字(元素)作为键和一些 bool 值作为索引的临时对象。

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

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');

附言设置慢 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');