javascript - 减少比较两个数组的时间。时间复杂度

Question

我需要一些关于更好方法的建议。假设我有 2 个要比较的数组，array1 和 array2，我需要检查数组 1 中的值是否存在于数组 2 中，在 PHP 中，我可以使用每次都有效的“array_diff”函数。

默认情况下，我想到的是迭代 array1，对于 array1 的每个值，再次比较 array2，两次迭代，这将是 (n*n) 时间复杂度，请参阅下面的代码。

我如何改进这个算法/​​代码。我的目标是检查一个数组中的值是否在另一个数组中。我如何改进这段代码，这样就不会花费这么多时间来比较两个数组。

const array1 = ["j1", "ff2", "3hj", "4sss", "5gh", "6ss", "7aqw"];
const array2 = ["klp3", "jks32", "44sss", "3hj", "5gh", "6ss", "7aqw"];

for (let index1 of array1){
  for (let index2 of array2){
    if (index1 === index2){
      console.log("Exists.", "index 1 value: " + index1, "Index 2 value: " + index2)
    }
  } 
}

我需要改进所花费的时间。另一个非二次的时间复杂度。

Answer 1

您可以选择 Set并检查另一个数组的每一项。

var array1 = ["j1", "ff2", "3hj", "4sss", "5gh", "6ss", "7aqw"],
    array2 = ["klp3", "jks32", "44sss", "3hj", "5gh", "6ss", "7aqw"],
    set1 = new Set(array1);

array2.forEach(v => {
    if (set1.has(v)) console.log(v);
});

如果您只想获取常见项目，您可以过滤数组。

var array1 = ["j1", "ff2", "3hj", "4sss", "5gh", "6ss", "7aqw"],
    array2 = ["klp3", "jks32", "44sss", "3hj", "5gh", "6ss", "7aqw"],
    common = array2.filter(Set.prototype.has, new Set(array1));

console.log(...common);