在 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 次瀏覽

開啟你的 職業生涯

完成課程並獲得認證

開始