Código mais simples para interseção de matriz em javascript

Qual é o código mais simples e livre de biblioteca para implementar interseções de matriz em javascript? eu quero escrever

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

e pegue

 [2, 3] 

Use uma combinação de Array.prototype.filter e Array.prototype.indexOf :

 array1.filter(value => -1 !== array2.indexOf(value)); 

Destrutivo parece mais simples, especialmente se pudermos supor que a input está ordenada:

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

Não-destrutivo tem que ser um cabelo mais complicado, já que temos que rastrear índices:

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

Se o seu ambiente suporta ECMAScript 6 Set , uma maneira simples e supostamente eficiente (veja o link da especificação):

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

Mais curto, mas menos legível (também sem criar o Set adicional de interseção):

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

Observe que a implementação do conjunto só permitirá valores exclusivos, portanto, o new Set[1,2,3,3].size avaliado como 3 .

Usando Underscore.js

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

Que tal usar apenas matrizes associativas?

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

editar:

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

Usando jQuery :

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

O desempenho da implementação do @ atk para ordenar matrizes de primitivos pode ser melhorado usando .pop em vez de .shift.

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

Eu criei um benchmark usando jsPerf: http://bit.ly/P9FrZK . É cerca de três vezes mais rápido usar o .pop.

Minha contribuição nos termos do ES6. Em geral, ele encontra a interseção de uma matriz com um número indefinido de matrizes fornecidas como argumentos.

 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("
" + JSON.stringify(arr.intersect(...arrs)) + "

");

  1. Ordenar isso
  2. verifique um por um a partir do índice 0, crie um novo array a partir dele.

Algo como isto, não testado bem embora.

 function intersection(x,y){ x.sort();y.sort(); var i=j=0;ret=[]; while(i 

PS: O algoritmo destinado apenas para Numbers e Normal Strings, a interseção de arrays de objects arbitrários pode não funcionar.

Para arrays que contenham apenas strings ou números, você pode fazer algo com a sorting, de acordo com algumas das outras respostas. Para o caso geral de matrizes de objects arbitrários, eu não acho que você possa evitar fazer isso por muito tempo. A seguir, você terá a interseção de qualquer número de matrizes fornecidas como parâmetros para 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"]; 

É bem curto usando ES2015 e Sets. Aceita valores como Array e remove duplicatas.

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

Um pequeno ajuste para o menor aqui (a solução filter / indexOf ), ou seja, criar um índice dos valores em um dos arrays usando um object JavaScript, irá reduzi-lo de O (N * M) para “provavelmente” tempo linear. source1 source2

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

Esta não é a solução mais simples (é mais código do que filter + indexOf ), nem é o mais rápido (provavelmente mais lento por um fator constante do que o intersect_safe () ), mas parece um bom equilíbrio. É do lado muito simples, proporcionando bom desempenho e não requer inputs pré-ordenadas.

 function intersection(A,B){ var result = new Array(); for (i=0; i 

Com algumas restrições em seus dados, você pode fazê-lo em tempo linear !

Para inteiros positivos : use um array mapeando os valores para um booleano “visto / não visto”.

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

Há uma técnica semelhante para objects : pegue uma chave fictícia, defina-a como "true" para cada elemento em array1 e, em seguida, procure por essa chave nos elementos de array2. Limpe quando estiver pronto.

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

É claro que você precisa ter certeza de que a chave não apareceu antes, senão você estará destruindo seus dados ...

Outra abordagem indexada capaz de processar qualquer número de matrizes de uma só vez:

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

Ele funciona apenas para valores que podem ser avaliados como strings e você deve passá-los como uma matriz como:

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

… mas transparentemente aceita objects como parâmetro ou como qualquer um dos elementos a serem interseccionados (sempre retornando matriz de valores comuns). Exemplos:

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

EDIT: só notei que isso é, de certa forma, um pouco buggy.

Ou seja: codifiquei pensando que as matrizes de input não podem conter repetições (como o exemplo fornecido não contém).

Mas se as matrizes de input contiverem repetições, isso produziria resultados errados. Exemplo (usando abaixo da implementação):

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

Felizmente, isso é fácil de resolver simplesmente adicionando a indexação de segundo nível. Isso é:

Mudança:

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

de:

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

…e:

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

de:

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

Exemplo completo:

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

Eu contribuirei com o que tem funcionado melhor para mim:

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

“indexOf” para IE 9.0, chrome, firefox, ópera,

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

Uma abordagem funcional com o ES2015

Uma abordagem funcional deve considerar usar apenas funções puras sem efeitos colaterais, cada uma das quais se preocupa apenas com um único trabalho.

Essas restrições aumentam a composibilidade e a capacidade de reutilização das funções envolvidas.

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

Pela simplicidade:

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

Benefícios:

  • sujeira simples
  • cinput em dados
  • funciona para um número arbitrário de listas
  • funciona para comprimentos arbitrários de listas
  • funciona para tipos arbitrários de valores
  • funciona para ordem de sorting arbitrária
  • retém forma (ordem da primeira aparição em qualquer array)
  • sai cedo, sempre que possível
  • memory segura, curta de adulteração com protótipos de function / matriz

Desvantagens:

  • maior uso de memory
  • maior uso da CPU
  • requer uma compreensão de reduzir
  • requer compreensão do stream de dados

Você não gostaria de usar isso para o mecanismo 3D ou para o trabalho do kernel, mas se você tiver problemas para fazer isso funcionar em um aplicativo baseado em events, seu design terá problemas maiores.

.reduce para construir um mapa e .filter para achar a interseção. delete dentro do .filter nos permite tratar o segundo array como se fosse um conjunto único.

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

Acho essa abordagem muito fácil de raciocinar. Ele executa em tempo constante.

Este é provavelmente o mais simples, além de list1.filter (n => list2.includes (n))

 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 

Aqui está a implementação do 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; }; 

Fonte: http://underscorejs.org/docs/underscore.html#section-62

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

Aqui está uma implementação muito ingênua que estou usando. Não é destrutivo e também garante não duplicar inputs.

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

interseção de N arrays em 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() 

Eu estendi a resposta do tarulen para trabalhar com qualquer número de matrizes. Também deve funcionar com valores não inteiros.

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

Building on Anon’s excellent answer, this one returns the intersection of two or more arrays.

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