在线性时间内查找数组中第一个重复项 JavaScript

javascriptweb developmentfront end technologyobject oriented programming更新于 2024/1/11 16:12:17

我们需要编写一个 JavaScript 函数，该函数接受一个只读数组，其中包含 1 到 n 之间的 n + 1 个整数。

该函数应在线性时间内找到一个重复的数字，并且最多使用 O(n) 空间。

例如，如果输入数组是 −

const arr = [3 4 1 4 1];

那么输出应该是 −

const output = 1;

如果有多个可能的答案(如上所示)，我们应该输出任何一个。如果没有重复，我们应该输出 -1。

示例

const arr = [3, 4, 1, 4, 1];
const findRepeatedNumber = (arr = []) => {
   const set = new Set();
   for (const item of arr) {
      if (set.has(item)){
         return item;
      };
      set.add(item);
   };
   return -1;
};
console.log(findRepeatedNumber(arr));