Javascript 数组匹配复杂度较低

Question

例如

inputarray = [1, 4, 5, 9];
array1 = [1, 2, 3, 4, 5, 6, 7];
array2 = [8, 9, 10, 11, 12, 13, 14];

我想将 inputarray 与 array1 和 array2 相匹配。在当前场景中，1,4,5 属于 array1，9 属于第二个数组。我期待类似的输出

outputarray1=[1,4,5]
outputarray2=[9]

建议我解决这个问题的最佳方法。我的意思是复杂性较低。提前致谢。

Answer 1

以空间为代价，您可以创建哈希对象并对包含内容进行恒定时间查找，而不是使用 O(n) indexOf 调用或 for 循环:

var inputarray = [1, 4, 5, 9];
var array1 = [1, 2, 3, 4, 5, 6, 7];
var array2 = [8, 9, 10, 11, 12, 13, 14];

var array1Hash = Object.create(null);
var array2Hash = Object.create(null);

var outputarray1 = [];
var outputarray2 = [];

array1.forEach(function(e) {
  array1Hash[e] = true;
});
array2.forEach(function(e) {
  array2Hash[e] = true;
});

inputarray.forEach(function(e) {
  if (e in array1Hash) {
    outputarray1.push(e);
  }
  if (e in array2Hash) {
    outputarray2.push(e);
  }
});

document.getElementById('out1').innerHTML = JSON.stringify(outputarray1);
document.getElementById('out2').innerHTML = JSON.stringify(outputarray2);

<pre id="out1"></pre>
<pre id="out2"></pre>