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

我们需要写一个 JavaScript 函数，这个函数接受一个只读数组，数组中有 n + 1 个 1 到 n 的整数。

这个函数应该在 O(n) 的时间复杂度和 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));

输出

将产生以下输出 -

4

AmitDiwan

更新于: 2020-11-25

250 次浏览

开启你的 职业生涯

完成课程并获得认证

开始