减少“firstDuplicate”的执行时间。算法 [英] Decrease execution time of "firstDuplicate" algorithm

问题描述

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

此函数返回数字数组中的第一个重复值。

This function returns the first duplicate value in the array of numbers.

我想减少执行时间。我应该做些什么改变？

I want to decrease its execution time. What changes should I do?

1. 对于 a = [2,3,3,1,5,2] ，输出应为 firstDuplicate（a）= 3 。

1. For a = [2, 3, 3, 1, 5, 2], the output should be firstDuplicate(a) = 3.

有两个重复：数字 2 和 3 。第二次出现 3 的索引小于第二次出现的 2 ，所以答案是 3 。

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than the second occurrence of 2 does, so the answer is 3.

1. 对于 a = [2 ，4,3,5,1] ，输出应为 firstDuplicate（a）= -1 。

1. For a = [2, 4, 3, 5, 1], the output should be firstDuplicate(a) = -1.

推荐答案

如果数组包含数字或字符串，你可以这样做，

If the array contains number or string you can do something like this,

//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]));

这篇关于减少“firstDuplicate”的执行时间。算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！