# JavaScript中数组交集的最简单代码

2020/09/23 00:21 · javascript ·  · 0评论

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

``[2, 3]``

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

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

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

``````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) {
var setB = new Set(b);
return [...new Set(a)].filter(x => setB.has(x));
}``````

``_.intersection( [0,345,324] , [1,0,324] )  // gives [0,324]``
``````// 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]));``````

Firefox 53中的结果：

• 大型阵列（10,000个元素）上的运算/秒：

``````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``````
• 小型阵列（100个元素）上的运算/秒：

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

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

``````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;
}``````
1. 解决
2. 从索引0逐一检查，从中创建新数组。

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

PS：仅适用于数字和普通字符串的算法，任意对象数组的交集可能不起作用。

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

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

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

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

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

With some restrictions on your data, you can do it in linear time!

For positive integers: use an array mapping the values to a "seen/not seen" boolean.

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

There is a similar technique for objects: take a dummy key, set it to "true" for each element in array1, then look for this key in elements of array2. Clean up when you're done.

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

Of course you need to be sure the key didn't appear before, otherwise you'll be destroying your data...

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

`.reduce`绘制地图并`.filter`找到相交点。`delete`中的`.filter`允许我们将第二个数组视为唯一的数组。

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

``````if arr1 = [{id: 10}, {id: 20}]
and arr2 =  [{id: 20}, {id: 25}]``````

``[{id: 20}]``

``````const intersect = (arr1, arr2, accessors = [v => v, v => v]) => {
const [fn1, fn2] = accessors;
const set = new Set(arr2.map(v => fn2(v)));
return arr1.filter(value => set.has(fn1(value)));
};``````

``intersect(arr1, arr2, [elem => elem.id, elem => elem.id])``

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

## ES2015的功能性方法

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

### 避免重复

``````// auxiliary functions

const apply = f => x => f(x);
const comp = f => g => x => f(g(x));
const afrom = apply(Array.from);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));

// intersection

const intersect = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? true
: false
) (xs);
};

// de-duplication

const dedupe = comp(afrom) (createSet);

// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];

// unique result

console.log( intersect(dedupe(xs)) (ys) );``````

### 计算任意数量的`Array`s 的交集

``````// auxiliary functions

const apply = f => x => f(x);
const uncurry = f => (x, y) => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const foldl = f => acc => xs => xs.reduce(uncurry(f), acc);

// intersection

const intersect = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? true
: false
) (xs);
};

// intersection of an arbitrarily number of Arrays

const intersectn = (head, ...tail) => foldl(intersect) (head) (tail);

// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
const zs = [0,1,2,3,4,5,6];

// run

console.log( intersectn(xs, ys, zs) );``````

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

• 简单的污垢
• 以数据为中心
• 适用于任意数量的列表
• 适用于任意长度的列表
• 适用于任意类型的值
• 适用于任意排序顺序
• 保持形状（任何阵列中的首次出现顺序）
• 尽可能提前退出
• 内存安全，不影响功能/阵列原型

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

``````var list1 = ['bread', 'ice cream', 'cereals', 'strawberry', 'chocolate']
var list2 = ['bread', 'cherry', 'ice cream', 'oats']

function check_common(list1, list2){

list3 = []
for (let i=0; i<list1.length; i++){

for (let j=0; j<list2.length; j++){
if (list1[i] === list2[j]){
list3.push(list1[i]);
}
}

}
return list3

}

check_common(list1, list2) // ["bread", "ice cream"]``````

``````const intersect = (a, b, ...rest) => {
if (rest.length === 0) return [...new Set(a)].filter(x => new Set(b).has(x));
return intersect(a, intersect(b, ...rest));
};

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

``````function intersection(arr1, arr2) {
var myObj = {};
var myArr = [];
for (var i = 0, len = arr1.length; i < len; i += 1) {
if(myObj[arr1[i]]) {
myObj[arr1[i]] += 1;
} else {
myObj[arr1[i]] = 1;
}
}
for (var j = 0, len = arr2.length; j < len; j += 1) {
if(myObj[arr2[j]] && myArr.indexOf(arr2[j]) === -1) {
myArr.push(arr2[j]);
}
}
return myArr;
}``````

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

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

``````function intersect_1d( a, b ){
var out=[], ai=0, bi=0, acurr, bcurr, last=Number.MIN_SAFE_INTEGER;
while( ( acurr=a[ai] )!==undefined && ( bcurr=b[bi] )!==undefined ){
if( acurr < bcurr){
if( last===acurr ){
out.push( acurr );
}
last=acurr;
ai++;
}
else if( acurr > bcurr){
if( last===bcurr ){
out.push( bcurr );
}
last=bcurr;
bi++;
}
else {
out.push( acurr );
last=acurr;
ai++;
bi++;
}
}
return out;
}``````
``````var arrays = [
[1, 2, 3],
[2, 3, 4, 5]
]
function commonValue (...arr) {
let res = arr[0].filter(function (x) {
return arr.every((y) => y.includes(x))
})
return res;
}
commonValue(...arrays);``````
``````function intersectionOfArrays(arr1, arr2) {
return arr1.filter((element) => arr2.indexOf(element) !== -1).filter((element, pos, self) => self.indexOf(element) == pos);
}``````