JavaScript中求两个数组交集的最简代码

Question

在JavaScript中，实现数组交集的最简单、无需使用库的代码是什么？我想编写

intersection([1,2,3], [2,3,4,5])

并获取

[2, 3]

- Peter

---

你想要简单还是快速？ - SLaks

优先级很简单，但不能太死板以至于成为性能瓶颈 :) - Peter

将 break 添加到 Simple js loops 中将会使 ops/sec 增加到约10M。 - Richard

不错！但是如果它们不是数字类型呢？如果它们是需要自定义检查的自定义对象呢？ - Yanick Rochon

测试中的函数返回错误的结果。实际上，只有一个实现返回了预期的结果。 - hegemon

Answer 1

使用 Array.prototype.filter 和 Array.prototype.includes 的组合：

const filteredArray = array1.filter(value => array2.includes(value));

对于较旧的浏览器，使用 Array.prototype.indexOf 并且没有箭头函数：

var filteredArray = array1.filter(function(n) {
    return array2.indexOf(n) !== -1;
});

注意！.includes和.indexOf内部使用===来比较数组中的元素，因此如果数组包含对象，则只会比较对象引用（而不是它们的内容）。如果要指定自己的比较逻辑，请改用Array.prototype.some。

- Anon.

---

这里的最佳答案既简单易懂，又适用于非数字工作。 - Muhd

intersection([1,2,1,1,3], [1]) 返回 [1, 1, 1]。它难道不应该只返回 [1] 吗？ - dev

好的，你需要一个第二个过滤器。请参考这个例子：https://dev59.com/hWQo5IYBdhLWcg3wOdJa#16227294（<--在那个答案的末尾） - loneboat

简洁易懂，适用于小型输入，但其复杂度为二次方。对于更大的输入，必须有更好的解决方案。 - Paul Rooney

这不是高度低效的吗，时间复杂度为 O(n^2)。 - paul23

Answer 2

如果我们可以假设输入已经排序，那么"destructive"似乎是最简单的方法：

/* destructively finds the intersection of 
 * two arrays in a simple fashion.  
 *
 * PARAMS
 *  a - first array, must already be sorted
 *  b - second array, must already be sorted
 *
 * NOTES
 *  State of input arrays is undefined when
 *  the function returns.  They should be 
 *  (prolly) be dumped.
 *
 *  Should have O(n) operations, where n is 
 *    n = MIN(a.length, b.length)
 */
function intersection_destructive(a, b)
{
  var result = [];
  while( a.length > 0 && b.length > 0 )
  {  
     if      (a[0] < b[0] ){ a.shift(); }
     else if (a[0] > b[0] ){ b.shift(); }
     else /* they're equal */
     {
       result.push(a.shift());
       b.shift();
     }
  }

  return result;
}

非破坏性操作必须更加复杂，因为我们必须跟踪索引：

/* finds the intersection of 
 * two arrays in a simple fashion.  
 *
 * PARAMS
 *  a - first array, must already be sorted
 *  b - second array, must already be sorted
 *
 * NOTES
 *
 *  Should have O(n) operations, where n is 
 *    n = MIN(a.length(), b.length())
 */
function intersect_safe(a, b)
{
  var ai=0, bi=0;
  var result = [];

  while( ai < a.length && bi < b.length )
  {
     if      (a[ai] < b[bi] ){ ai++; }
     else if (a[ai] > b[bi] ){ bi++; }
     else /* they're equal */
     {
       result.push(a[ai]);
       ai++;
       bi++;
     }
  }

  return result;
}

- atk

---

array.shift每次调用时都会在底层创建一个新的数组吗？ - thesmart

@thesmart：你说得对，肯定有更高效的方法来实现。上面的代码旨在简单易懂，而不是快速执行 :) - atk

.shift需要移动数组中的每个元素（本身是O(n)），因此第一个版本复杂度的评论是错误的。 - Esailija

不，循环停止的条件是其中一个数组已经完成了遍历，而不一定是较短的那个数组。请参考这个例子。 - Shawn

破坏性版本消除了需要排序数组的优势：不会以二次时间运行。我认为它甚至没有提高可读性。将其编辑为仅快速、非破坏性版本会使答案更好。 - Ry-

Answer 3

如果您的环境支持ECMAScript 6 Set，则有一种简单且据说高效的方法（请参见规范链接）：

function intersect(a, b) {
  var setA = new Set(a);
  var setB = new Set(b);
  var intersection = new Set([...setA].filter(x => setB.has(x)));
  return Array.from(intersection);
}

更短，但可读性较差（也不需要创建额外交集的Set）：

function intersect(a, b) {
  var setB = new Set(b);
  return [...new Set(a)].filter(x => setB.has(x));
}

请注意，使用集合时，您将仅获得不同的值，因此 new Set([1, 2, 3, 3]).size 将计算为 3。

- nbarbosa

---

这个[...setA]语法是什么？是一种特殊的JavaScript操作吗？ - jxramos

@jxramos 这是展开语法，这种情况下它只是用来从集合中的元素创建数组。在这种情况下，“Array.from(setA)”也可以工作，但由于问题要求“简单”，我试图让它更清晰，更易读。关于这个问题，我认为代码可以更简洁，所以我会更新代码片段。 - nbarbosa

请注意，集合实现只允许唯一的值 - 这是“Set”的字面定义，而不是实现细节。 - Madbreaks

使用Set的优势是什么？为什么不能只用标准数组来完成它？ - adelriosantiago

在第一个例子中（去重），不需要从a和intersection都创建一个集合。只需要其中一个即可。 - Ry-

Answer 4

使用 Underscore.js 或 lodash.js

_.intersection( [0,345,324] , [1,0,324] )  // gives [0,324]

- Sai Ram

---

Op要求“无需使用库”。 - LinuxDisciple

无论如何，这是该搜索的谷歌排名最高的结果，因此有一个图书馆的回答非常有用。谢谢。 - webnoob

这是一种不错的方法，但我想知道哪个更快/更有效：arrA.filter(e=>e.includes(arrB)) 或者_.intersection(arrA, arrB)？ - Ivancho

嗨，是否有可能将一个列表的列表传递给这个函数？例如[ [ { tokenId: 2 } ], [ { tokenId: 2 }, { tokenId: 3 } ] ]并期望它返回{ tokenId: 2 }？ - ansh sachdeva

@anshsachdeva 是的，你可以这样做： var objects = [ [ { tokenId: 2 } ] ] var others = [ [ { tokenId: 2 }, { tokenId: 3 } ] ] _.intersectionWith(objects, others, (a, b) => _.intersectionWith(a, b)); - Harshil Modi

Answer 5

// Return elements of array a that are also in b in linear time:
function intersect(a, b) {
  return a.filter(Set.prototype.has, new Set(b));
}

// Example:
console.log(intersect([1,2,3], [2,3,4,5]));

我建议使用简洁的解决方案，它在处理大型输入时优于其他实现。如果小型输入的性能很重要，请查看下面的替代方案。

备选方案和性能比较：

请查看以下代码段以获取替代实现，并查看https://jsperf.com/array-intersection-comparison进行性能比较。

function intersect_for(a, b) {
  const result = [];
  const alen = a.length;
  const blen = b.length;
  for (let i = 0; i < alen; ++i) {
    const ai = a[i];
    for (let j = 0; j < blen; ++j) {
      if (ai === b[j]) {
        result.push(ai);
        break;
      }
    }
  } 
  return result;
}

function intersect_filter_indexOf(a, b) {
  return a.filter(el => b.indexOf(el) !== -1);
}

function intersect_filter_in(a, b) {
  const map = b.reduce((map, el) => {map[el] = true; return map}, {});
  return a.filter(el => el in map);
}

function intersect_for_in(a, b) {
  const result = [];
  const map = {};
  for (let i = 0, length = b.length; i < length; ++i) {
    map[b[i]] = true;
  }
  for (let i = 0, length = a.length; i < length; ++i) {
    if (a[i] in map) result.push(a[i]);
  }
  return result;
}

function intersect_filter_includes(a, b) {
  return a.filter(el => b.includes(el));
}

function intersect_filter_has_this(a, b) {
  return a.filter(Set.prototype.has, new Set(b));
}

function intersect_filter_has_arrow(a, b) {
  const set = new Set(b);
  return a.filter(el => set.has(el));
}

function intersect_for_has(a, b) {
  const result = [];
  const set = new Set(b);
  for (let i = 0, length = a.length; i < length; ++i) {
    if (set.has(a[i])) result.push(a[i]);
  }
  return result;
}

在 Firefox 53 中的结果：

• Ops/sec on large arrays (10,000 elements):

  filter + has (this)               523 (this answer)
  for + has                         482
  for-loop + in                     279
  filter + in                       242
  for-loops                          24
  filter + includes                  14
  filter + indexOf                   10
  

• Ops/sec on small arrays (100 elements):

  for-loop + in                 384,426
  filter + in                   192,066
  for-loops                     159,137
  filter + includes             104,068
  filter + indexOf               71,598
  filter + has (this)            43,531 (this answer)
  filter + has (arrow function)  35,588
  

- le_m

---

intersect([1,2,2,3], [2,3,4,5]) 的返回值为 [2, 2, 3]。 - SeregPie

@SeregPie 没错。根据评论“返回数组a中也存在于b中的元素”。 - le_m

回答质量很高，但使用集合会从根本上改变结果，因为op的问题仅询问数组交集，并未提及/规定如何处理重复项。除此之外，当存在重复项时，此答案可能会产生意外的结果。 - Madbreaks

Answer 6

用ES6术语描述我的贡献。通常它会在提供的无限数量的数组中找到交集。

Array.prototype.intersect = function(...a) {
  return [this,...a].reduce((p,c) => p.filter(e => c.includes(e)));
}
var arrs = [[0,2,4,6,8],[4,5,6,7],[4,6]],
     arr = [0,1,2,3,4,5,6,7,8,9];

document.write("<pre>" + JSON.stringify(arr.intersect(...arrs)) + "</pre>");

- Redu

---

这段代码看起来很棒，但我并不完全理解。能否请你解释一下吗？ - theusual

@novembersky 它将所有主题数组收集到一个数组中，例如[[0,1,2,3,4,5,6,7,8,9],[0,2,4,6,8],[4,5,6,7],[4,6]]，然后应用.reduce()。首先执行[0,1,2,3,4,5,6,7,8,9].filter( e => [0,2,4,6,8].includes(e)操作，并且结果成为新的p，在下一轮中c变成[4,5,6,7]，并继续进行，直到没有剩余的c。 - Redu

如果您处理的是大型数据集，这将是一种昂贵的解决方案。 - Madbreaks

不要不必要地修改 prototype。 - fregante

如果你确实想修改 Array.prototype，那么请正确地进行操作。 - Bergi

Answer 7

最简单、最快的O(n)和最短的方法：

function intersection (a, b) {
    const setA = new Set(a);
    return b.filter(value => setA.has(value));
}

console.log(intersection([1,2,3], [2,3,4,5]))

@nbarbosa几乎给出了相同的答案，但他将两个数组都转换为Set，然后再转回array。不同之处在于，他的代码只会返回唯一的记录，而此代码的结果还将包含来自数组b的重复条目（假设两个数组没有填入唯一值）。

所以使用符合您要求的任何代码即可。

- NoOorZ24

Answer 8

使用关联数组如何？

function intersect(a, b) {
    var d1 = {};
    var d2 = {};
    var results = [];
    for (var i = 0; i < a.length; i++) {
        d1[a[i]] = true;
    }
    for (var j = 0; j < b.length; j++) {
        d2[b[j]] = true;
    }
    for (var k in d1) {
        if (d2[k]) 
            results.push(k);
    }
    return results;
}

编辑：

// new version
function intersect(a, b) {
    var d = {};
    var results = [];
    for (var i = 0; i < b.length; i++) {
        d[b[i]] = true;
    }
    for (var j = 0; j < a.length; j++) {
        if (d[a[j]]) 
            results.push(a[j]);
    }
    return results;
}

- Steven Huwig

---

只有当您的数组仅包含字符串或数字，并且页面中的脚本没有干扰Object.prototype时，这才有可能成功。 - Tim Down

原文：The OP's example was using numbers, and if a script has messed with Object.prototype then the script should be rewritten or removed.翻译：原帖例子中使用了数字，如果脚本已经篡改了 Object.prototype，则应该重新编写或删除该脚本。 - Steven Huwig

你不需要同时使用 (d1) 和 (d2)。先创建 (d2)，然后通过循环 (a) 而不是循环 (d1)。 - StanleyH

应该是 d[b[i]] = true; 而不是 d[b[j]] = true;（使用 i 而不是 j）。但修改需要 6 个字符。 - Izhaki

@Izhaki 谢谢，问题已修复。（添加了一个//注释以满足最小编辑要求。） - Steven Huwig

这个函数的一个好的副作用是：它保证结果将按照初始的“a”数组排序。为了可能的速度提升，我会在函数开始时简单地缓存a.length和b.length，即var d = {}，results = []，alen = a.length，blen = b.length; - Louis LC

Answer 9

如果您需要处理相交的多个数组：

const intersect = (a1, a2, ...rest) => {
  const a12 = a1.filter(value => a2.includes(value))
  if (rest.length === 0) { return a12; }
  return intersect(a12, ...rest);
};

console.log(intersect([1,2,3,4,5], [1,2], [1, 2, 3,4,5], [2, 10, 1])) 

- Belfordz

---

但是对于30个具有100个元素的数组，这个解决方案有多快？ - aidonsnous

这只使用了纯粹的JavaScript方法，因此运行代码的虚拟机可以自由地优化它。我非常确信，如果在现代版本的V8中运行此代码，不存在比它更快的解决方案，相对于本评论的年龄而言。 - Belfordz

@Belfordz：不，这样做非常慢，因为涉及到大量的数组复制和不必要的集合重构。仅使用b.includes(x)比使用new Set(b).has(x)甚至更慢。 - Ry-

Answer 10

使用 .pop 而不是 .shift 可以提高 @atk 实现的原始数组排序性能。

function intersect(array1, array2) {
   var result = [];
   // Don't destroy the original arrays
   var a = array1.slice(0);
   var b = array2.slice(0);
   var aLast = a.length - 1;
   var bLast = b.length - 1;
   while (aLast >= 0 && bLast >= 0) {
      if (a[aLast] > b[bLast] ) {
         a.pop();
         aLast--;
      } else if (a[aLast] < b[bLast] ){
         b.pop();
         bLast--;
      } else /* they're equal */ {
         result.push(a.pop());
         b.pop();
         aLast--;
         bLast--;
      }
   }
   return result;
}

我使用jsPerf创建了一个基准测试。使用.pop方法可以使速度快三倍。

- xn.

---

只是提醒其他人注意，这仅适用于数字，而不是字符串。 - Izhaki

请注意，如果您将 a[aLast] > b[bLast] 替换为 a[aLast].localeCompare(b[bLast]) > 0（并且下面的 else if 同样如此），那么它将适用于字符串。 - andrew

速度差异取决于数组的大小，因为 .pop 的时间复杂度是 O(1)，而 .shift() 的时间复杂度是 O(n)。 - Esailija