# 在javascript中最简单的数组交集

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

` `[2, 3]` `

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

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

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

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

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

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

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

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

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

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

` `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，任意对象数组的交集可能不起作用。

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

` `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"];` `

` `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(''));` `

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

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

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

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

` `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"]` `

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

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

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]` `
` `'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))` `

## 采用ES2015的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) );` `

` `// 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

` `_.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; };` `

` `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 ]` `

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

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()` `

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

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

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

`.reduce`减lessbuild立一个地图，和`.filter`find交集。 在`.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; }); }` `