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

Question

这是一个亚马逊的采访问题,我的回答是

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.length,n = B.length

并且他说有更好的方法可以做到这一点我就像WTF ??????? 他说使用A和B对象和我一样

"但你说这些是阵列那是你的问题!!!!"

有人可以帮帮我吗？

Answer 1

如果您知道数组值是字符串或数字,则可以创建一个对象,该对象将值作为属性名称和每个值的truthy值.然后,您可以在传递第二个数组时使用简单对象查找.

就像是:

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