Уменьшить время выполнения алгоритма "firstDuplicate"

Question

function firstDuplicate(a) {
  var numbers = {},
      res;

foo:
  for (var i = 0; i < a.length; i++) {
    for (var j = i + 1; j < a.length; j++) {
      if (a[i] === a[j]) {
        numbers[a[i]] = j - i;
        if (j - i === 1 ) {
            break foo;
        }
      }
    }
  }

  var keys = Object.keys(numbers),
      res = keys[0];

  keys.forEach(function (v) {
    res = numbers[res] > numbers[v] ? v : res;
  });

  console.log(res);

  return res === undefined ? -1 : Number(res);
}

Эта функция возвращает первое дублированное значение в массиве чисел.

Я хочу уменьшить время его исполнения. Какие изменения я должен сделать?

Примеры

1. За a = [2, 3, 3, 1, 5, 2]выход должен быть firstDuplicate(a) = 3,

Есть 2 дубликата: номера 2 а также 3, Второе появление 3 имеет меньший индекс, чем второе вхождение 2 да, так что ответ 3,

2. За a = [2, 4, 3, 5, 1]выход должен быть firstDuplicate(a) = -1,

Answer 1

Если массив содержит число или строку, вы можете сделать что-то вроде этого,

//Returns the first duplicate element   
function firstDup(arr) {
  let o = {}; //an empty object
  for (let i = 0; i < arr.length; i++) {
    if (o[arr[i]]) { //check if the property exists
      return arr[i];
    } else {
      o[arr[i]] = 'a'; //set the object's property to something non falsy
    }
  }
  return -1; //If No duplicate found return -1
}

console.log(firstDup([2, 3, 3, 1, 5, 2]));
console.log(firstDup([2, 4, 3, 5, 1]));

Answer 2

function firstDuplicate(array) {
  const numbers = {};
  
  for (const number of array) {
    if (numbers[number]) {
      return number;
    } else {
      numbers[number] = true;
    }
  }
  
  return -1; // No duplicate
}

const duplicate = firstDuplicate([1, 2, 3, 4, 5, 6, 10, 1, 3]);
console.log(duplicate)

Answer 3

Вы можете вместо этого использовать find а также indexOf:

 function findFirstDupe(array) {
   return array.find((n, i) => array.indexOf(n) !== i);
 }

Или вы используете набор для проверки предыдущих появлений:

function findFirstDupe(array){
  const set = new Set();
  return array.find(n => set.has(n) || (set.add(n), false));
}

То же самое с объектом в виде хэша:

function findFirstDupe(array){
  const hash = {};
  return array.find(n => !(hash[n] = !hash[n]))
}