在javascript中最简单的数组交集

什么是最简单的，在JavaScript中实现数组相交的无库代码？ 我想写

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

并得到

 [2, 3] 

Answer 1

破坏性似乎最简单，特别是如果我们可以假设input是sorting的：

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

Answer 2

.filter第一个数组也包含在第二个元素中！

 array1.filter((n) => array2.includes(n)) 

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

较短，但较less可读（也不创build额外的交集）：

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

请注意，集合实现将只允许唯一值，因此new Set[1,2,3,3].size计算结果为3 。

Answer 4

使用Underscore.js

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

Answer 5

我也想在这里添加这个方法

 var a = [1,2,3]; var b = [2,3,4,5]; var c = $(b).not($(b).not(a)); alert(c); 

Answer 6

如何使用关联数组？

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

Answer 7

使用.pop而不是.shift可以改进@ atk对sorting的基元数组的执行性能。

 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创build了一个基准： http ://bit.ly/P9FrZK。 使用.pop的速度要快三倍。

Answer 8

1. 分类
2. 从索引0中逐个检查，从中创build新的数组。

像这样的东西，虽然没有很好的testing。

 function intersection(x,y){ x.sort();y.sort(); var i=j=0;ret=[]; while(i<x.length && j<y.length){ if(x[i]<y[j])i++; else if(y[j]<x[i])j++; else { ret.push(x[i]); i++,j++; } } return ret; } alert(intersection([1,2,3], [2,3,4,5])); 

PS：该algorithm仅用于Numbers和Normal Strings，任意对象数组的交集可能不起作用。

Answer 9

我在ES6中的贡献。 一般来说，它会find一个数组的交集，其数组的数量是不定的。

 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>"); 

Answer 10

对于只包含string或数字的数组，您可以按照其他一些答案来进行sorting。 对于任意对象数组的一般情况，我不认为你可以避免这么长的路。 以下将给你提供作为arrayIntersection参数的任意数量的数组的arrayIntersection ：

 var arrayContains = Array.prototype.indexOf ? function(arr, val) { return arr.indexOf(val) > -1; } : function(arr, val) { var i = arr.length; while (i--) { if (arr[i] === val) { return true; } } return false; }; function arrayIntersection() { var val, arrayCount, firstArray, i, j, intersection = [], missing; var arrays = Array.prototype.slice.call(arguments); // Convert arguments into a real array // Search for common values firstArray = arrays.pop(); if (firstArray) { j = firstArray.length; arrayCount = arrays.length; while (j--) { val = firstArray[j]; missing = false; // Check val is present in each remaining array i = arrayCount; while (!missing && i--) { if ( !arrayContains(arrays[i], val) ) { missing = true; } } if (!missing) { intersection.push(val); } } } return intersection; } arrayIntersection( [1, 2, 3, "a"], [1, "a", 2], ["a", 1] ); // Gives [1, "a"]; 

Answer 11

使用ES2015和Sets很短。 接受像数组一样的类似数组的值，并删除重复项。

 let intersection = function(a, b) { a = new Set(a), b = new Set(b); return [...a].filter(v => b.has(v)); }; console.log(intersection([1,2,1,2,3], [2,3,5,4,5,3])); console.log(intersection('ccaabbab', 'addb').join('')); 

Answer 12

对这里最小的一个（ filter / indexOf解决scheme ）进行微调，即使用JavaScript对象为其中一个数组创build索引值，将从O（N * M）降低到“可能”线性时间。 source1 source2

 function intersect(a, b) { var aa = {}; a.forEach(function(v) { aa[v]=1; }); return b.filter(function(v) { return v in aa; }); } 

这不是最简单的解决scheme（它比filter + indexOf更多的代码），也不是最快的（可能比intersect_safe（）慢一个常数），但似乎是一个很好的平衡。 这是非常简单的一面，同时提供良好的性能，而且不需要预先分类的input。

Answer 13

对数据有一些限制，可以在线性时间内完成！

对于正整数 ：使用将值映射到“看到/未看到”布尔值的数组。

 function intersectIntegers(array1,array2) { var seen=[], result=[]; for (var i = 0; i < array1.length; i++) { seen[array1[i]] = true; } for (var i = 0; i < array2.length; i++) { if ( seen[array2[i]]) result.push(array2[i]); } return result; } 

对于对象有一个类似的技术：对于array1中的每个元素，使用一个虚拟键，将其设置为“true”，然后在array2的元素中查找该键。 清理完成后。

 function intersectObjects(array1,array2) { var result=[]; var key="tmpKey_intersect" for (var i = 0; i < array1.length; i++) { array1[i][key] = true; } for (var i = 0; i < array2.length; i++) { if (array2[i][key]) result.push(array2[i]); } for (var i = 0; i < array1.length; i++) { delete array1[i][key]; } return result; } 

当然，你需要确定键没有出现，否则你会摧毁你的数据…

Answer 14

另一种能够同时处理任意数量的数组的索引方法：

 // Calculate intersection of multiple array or object values. function intersect (arrList) { var arrLength = Object.keys(arrList).length; // (Also accepts regular objects as input) var index = {}; for (var i in arrList) { for (var j in arrList[i]) { var v = arrList[i][j]; if (index[v] === undefined) index[v] = 0; index[v]++; }; }; var retv = []; for (var i in index) { if (index[i] == arrLength) retv.push(i); }; return retv; }; 

它只适用于可以作为string评估的值，并且应该像数组一样传递它们：

 intersect ([arr1, arr2, arr3...]); 

…但它透明地接受对象作为参数或任何要相交的元素（总是返回通用值的数组）。 例子：

 intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4] intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"] 

编辑：我只是注意到，这是，在某种程度上，有点越野车。

那就是：我编码它认为input数组本身不能包含重复（如提供的例子不）。

但是，如果input数组碰巧包含重复，那就会产生错误的结果。 示例（使用下面的实现）：

 intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // Expected: [ '1' ] // Actual: [ '1', '3' ] 

幸运的是，只需添加二级索引就可以很容易地解决这个问题。 那是：

更改：

  if (index[v] === undefined) index[v] = 0; index[v]++; 

通过：

  if (index[v] === undefined) index[v] = {}; index[v][i] = true; // Mark as present in i input. 

…和：

  if (index[i] == arrLength) retv.push(i); 

通过：

  if (Object.keys(index[i]).length == arrLength) retv.push(i); 

完整的例子：

 // Calculate intersection of multiple array or object values. function intersect (arrList) { var arrLength = Object.keys(arrList).length; // (Also accepts regular objects as input) var index = {}; for (var i in arrList) { for (var j in arrList[i]) { var v = arrList[i][j]; if (index[v] === undefined) index[v] = {}; index[v][i] = true; // Mark as present in i input. }; }; var retv = []; for (var i in index) { if (Object.keys(index[i]).length == arrLength) retv.push(i); }; return retv; }; intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // [ '1' ] 

Answer 15

 // 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])); 

Answer 16

 function intersection(A,B){ var result = new Array(); for (i=0; i<A.length; i++) { for (j=0; j<B.length; j++) { if (A[i] == B[j] && $.inArray(A[i],result) == -1) { result.push(A[i]); } } } return result; } 

Answer 17

我会为我做出最适合自己的事情做出贡献：

 if (!Array.prototype.intersect){ Array.prototype.intersect = function (arr1) { var r = [], o = {}, l = this.length, i, v; for (i = 0; i < l; i++) { o[this[i]] = true; } l = arr1.length; for (i = 0; i < l; i++) { v = arr1[i]; if (v in o) { r.push(v); } } return r; }; } 

Answer 18

IE 9.0的“indexOf”，chrome，firefox，opera，

  function intersection(a,b){ var rs = [], x = a.length; while (x--) b.indexOf(a[x])!=-1 && rs.push(a[x]); return rs.sort(); } intersection([1,2,3], [2,3,4,5]); //Result: [2,3] 

Answer 19

 'use strict' // Example 1 function intersection(a1, a2) { return a1.filter(x => a2.indexOf(x) > -1) } // Example 2 (prototype function) Array.prototype.intersection = function(arr) { return this.filter(x => arr.indexOf(x) > -1) } const a1 = [1, 2, 3] const a2 = [2, 3, 4, 5] console.log(intersection(a1, a2)) console.log(a1.intersection(a2)) 

Answer 20

采用ES2015的function性方法

function方法必须考虑只使用纯function而没有副作用，每个function都只涉及单个工作。

这些限制增强了所涉及function的可组合性和可重用性。

 // small, reusable auxiliary functions const createSet = xs => new Set(xs); const filter = f => xs => xs.filter(apply(f)); const apply = f => x => f(x); // intersection const intersect = xs => ys => { const zs = createSet(ys); return filter(x => zs.has(x) ? true : false ) (xs); }; // mock data const xs = [1,2,2,3,4,5]; const ys = [0,1,2,3,3,3,6,7,8,9]; // run it console.log( intersect(xs) (ys) ); 

Answer 21

为了简单：

 // Usage const intersection = allLists .reduce(intersect, allValues) .reduce(removeDuplicates, []); // Implementation const intersect = (intersection, list) => intersection.filter(item => list.some(x => x === item)); const removeDuplicates = (uniques, item) => uniques.includes(item) ? uniques : uniques.concat(item); // Example Data const somePeople = [bob, doug, jill]; const otherPeople = [sarah, bob, jill]; const morePeople = [jack, jill]; const allPeople = [...somePeople, ...otherPeople, ...morePeople]; const allGroups = [somePeople, otherPeople, morePeople]; // Example Usage const intersection = allGroups .reduce(intersect, allPeople) .reduce(removeDuplicates, []); intersection; // [jill] 

优点：

• 污垢简单
• 数据中心
• 适用于任意数量的列表
• 适用于任意长度的列表
• 适用于任意types的值
• 适用于任意sorting顺序
• 保留形状（任何arrays中的第一次出现的次序）
• 尽可能早退出
• 内存安全，不会篡改函数/数组原型

缺点：

• 更高的内存使用
• 更高的CPU使用率
• 需要了解减less
• 需要了解数据stream

您不希望将其用于3D引擎或内核工作，但如果您在基于事件的应用程序中运行时遇到问题，那么您的devise会遇到更大的问题。

Answer 22

这里是underscore.js的实现：

 _.intersection = function(array) { if (array == null) return []; var result = []; var argsLength = arguments.length; for (var i = 0, length = array.length; i < length; i++) { var item = array[i]; if (_.contains(result, item)) continue; for (var j = 1; j < argsLength; j++) { if (!_.contains(arguments[j], item)) break; } if (j === argsLength) result.push(item); } return result; }; 

资料来源： http ： //underscorejs.org/docs/underscore.html#section-62

Answer 23

 function getIntersection(arr1, arr2){ var result = []; arr1.forEach(function(elem){ arr2.forEach(function(elem2){ if(elem === elem2){ result.push(elem); } }); }); return result; } getIntersection([1,2,3], [2,3,4,5]); // [ 2, 3 ] 

Answer 24

这是我正在使用的一个非常天真的实现。 这是非破坏性的，也确保不重复entires。

 Array.prototype.contains = function(elem) { return(this.indexOf(elem) > -1); }; Array.prototype.intersect = function( array ) { // this is naive--could use some optimization var result = []; for ( var i = 0; i < this.length; i++ ) { if ( array.contains(this[i]) && !result.contains(this[i]) ) result.push( this[i] ); } return result; } 

Answer 25

N个数组在Coffeescript中的交集

 getIntersection: (arrays) -> if not arrays.length return [] a1 = arrays[0] for a2 in arrays.slice(1) a = (val for val in a1 when val in a2) a1 = a return a1.unique() 

Answer 26

我将tarulen的答案扩展到了任何数组。 它也应该使用非整数值。

 function intersect() { const last = arguments.length - 1; var seen={}; var result=[]; for (var i = 0; i < last; i++) { for (var j = 0; j < arguments[i].length; j++) { if (seen[arguments[i][j]]) { seen[arguments[i][j]] += 1; } else if (!i) { seen[arguments[i][j]] = 1; } } } for (var i = 0; i < arguments[last].length; i++) { if ( seen[arguments[last][i]] === last) result.push(arguments[last][i]); } return result; } 

Answer 27

 var listA = [1,2,3,4,5,6,7]; var listB = [2,4,6,8]; var result = listA.filter(itemA=> { return listB.some(itemB => itemB === itemA); }); 

Answer 28

build立在匿名的优秀答案，这个返回两个或更多的数组的交集。

 function arrayIntersect(arrayOfArrays) { var arrayCopy = arrayOfArrays.slice(), baseArray = arrayCopy.pop(); return baseArray.filter(function(item) { return arrayCopy.every(function(itemList) { return itemList.indexOf(item) !== -1; }); }); } 

Answer 29

希望这有助于所有版本。

 function diffArray(arr1, arr2) { var newArr = []; var large = arr1.length>=arr2.length?arr1:arr2; var small = JSON.stringify(large) == JSON.stringify(arr1)?arr2:arr1; for(var i=0;i<large.length;i++){ var copyExists = false; for(var j =0;j<small.length;j++){ if(large[i]==small[j]){ copyExists= true; break; } } if(!copyExists) { newArr.push(large[i]); } } for(var i=0;i<small.length;i++){ var copyExists = false; for(var j =0;j<large.length;j++){ if(large[j]==small[i]){ copyExists= true; break; } } if(!copyExists) { newArr.push(small[i]); } } return newArr; } 

Answer 30

.reduce减lessbuild立一个地图，和.filterfind交集。 在.filter delete允许我们把第二个数组看作是一个唯一的集合。

 function intersection (a, b) { var seen = a.reduce(function (h, k) { h[k] = true; return h; }, {}); return b.filter(function (k) { var exists = seen[k]; delete seen[k]; return exists; }); } 

我觉得这个方法很容易推理。 它在不变的时间执行。