在Javascript中查找两个数组的交集

Question

在Javascript中查找两个数组的交集

javascriptalgorithmoptimizationdata-structures

3

这是我在亚马逊面试中遇到的一个问题，我的答案是

function intersection ( A , B ) 
{
    var C = [];
    for ( var a in A ) if ( B.indexOf(a) != -1 ) C.push(a);
    return C;
}

他问复杂度的顺序是什么，我回答道并且引用：O(m * n)，其中 m=A 的长度，n=B 的长度。他说有更好的方法来做，我当时很惊讶。他说要把 A 和 B 作为对象使用，而我却像是在说：“但你说这些是数组啊！那是你的问题！！！”请问有人能帮帮我吗？

- user5377020

我不确定“用作对象”如何有帮助，但如果在开始之前从B创建一个查找表（字典），那么您可以在O(n)中完成它。 - Lee

3

在JavaScript面试中，不要使用 for ... in 循环遍历数组。 - Pointy

1

顺便说一句，关于这个问题在SO上有很多类似的问题，例如：https://dev59.com/kXI-5IYBdhLWcg3wYnOQ。 - Lee

从B创建一个查找表需要触及B的每个元素以及插入字典的复杂度。复杂度将保持为O(m * n)。 - Jon Trauntvein

1

@JonTrauntvein 不，它将是O(n+m)，这实际上只是O(n)。 - Lee

2

如果A和B是数组，这段代码并不会像它所表现的那样运行。在for (var a in A) { ... }中，变量a将保存索引。 - Andreas

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pointy · Accepted Answer

如果您知道数组值是字符串或数字，您可以创建一个对象，该对象将值作为属性名称，并对每个属性名称赋予真值。然后，您可以在第二个数组中使用简单的对象查找。

例如：

function intersection ( A , B ) 
{
    var m = A.reduce(function(m, v) { m[v] = 1; return m; }, {});
    return B.filter(function(v) { return m[v]; });
}

编辑 - 为了从结果中删除重复项，可以使用另一个.reduce()操作：

function intersection ( A , B ) 
{
    var m = A.reduce(function(m, v) { m[v] = 1; return m; }, {});
    return B.reduce(function(rv, v) {
      if (!rv.m[v]) {
        rv.m[v] = 1;
        rv.l.push(v);
      }
      return rv;
    }, {m:{}, l:[]}).l;
}