在Javascript中查找两个数组的交集 [英] Finding the intersection of two arrays in Javascript

问题描述

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

This was an Amazon interview question I had an my answer was

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

他问我复杂的顺序是什么，我说，我引用确切地说，

and he asked what the order of complexity was and I said, and I quote exactly,

O（m * n）其中m = A.length和n = B.length

O(m * n) where m=A.length and n=B.length

他正在说有一个更好的方法来做，我就像WTF ???他正在使用 A 和 B 作为对象，我就像

and he was saying there's a better way to do it and I was like WTF??????? He was saying use A and B as Objects and I was like

但是你说这些是数组这是你的问题!!!!

"But you said these were arrays That was your question!!!!"

有人可以帮助我吗？

推荐答案

如果你知道数组值是字符串或数字，您可以创建一个对象，其值为每个的属性名称和真实值。然后，您可以在通过第二个数组的过程中使用简单的对象查找。

If you know that the array values are strings or numbers, you can create an object that's got the values as property names and truthy values for each. Then you can use simple object lookup in a pass through the second array.

如下所示：

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（） pass：

edit — to remove duplicates from the result, another .reduce() pass could be used:

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

这篇关于在Javascript中查找两个数组的交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！