El código más simple para la intersección de matrices en javascript

611

¿Cuál es el código más simple y sin biblioteca para implementar intersecciones de matriz en javascript? Quiero escribir

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

y obten

[2, 3]
Peter
fuente
16
¿Quieres simple o rápido?
SLaks
11
Prioridad es simple, pero no puede ser tan muerte cerebral que será un cerdo rendimiento :)
Peter
44
He creado una página de prueba JsFiddle Banchmark para todos los métodos aquí, incluida lafunción de intersección _underscore . (más alto es mejor) ! ingrese la descripción de la imagen aquí Hasta ahora intersect_safe dio los mejores resultados . TÚ y subrayar lo peor.
neoswf
Agregar breaka Simple js loopsaumenta las operaciones por segundo a ~ 10M
Richard
19
En caso de que se lo pierda : la respuesta más simple no es la aceptada, sino la de abajo: stackoverflow.com/questions/1885557/…
redben

Respuestas:

1081

Use una combinación de Array.prototype.filtery Array.prototype.indexOf:

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

O como vrugtehagel sugirió en los comentarios, puede usar el Array.prototype.includescódigo más reciente para un código aún más simple:

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

Para navegadores antiguos:

array1.filter(function(n) {
    return array2.indexOf(n) !== -1;
});
Luego.
fuente
99
Lo que puede resolver agregando una versión de biblioteca en el prototipo de la matriz.
Anon
12
Sí, pero valió la pena mencionarlo.
Tim Down
18
La mejor respuesta aquí, tanto por simplicidad como por trabajar con números que no son
Muhd
41
intersection([1,2,1,1,3], [1])vuelve [1, 1, 1]. ¿No debería volver solo [1]?
edjroot
21
En lugar de array2.indexOf(n) != -1uno, también puede escribir array2.includes(n)para un código aún más simple.
vrugtehagel
157

Destructivo parece más simple, especialmente si podemos suponer que la entrada 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;
}

No destructivo tiene que ser un cabello más complicado, ya que tenemos 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;
}
atk
fuente
14
Hay numerosos errores en intersect_safe: lengthes una propiedad en Matrices, no un método. Hay una variable sin demora ien result.push(a[i]);. Finalmente, esto simplemente no funciona en el caso general: dos objetos donde ninguno es mayor que el otro según el >operador no son necesariamente iguales. intersect_safe( [ {} ], [ {} ] ), por ejemplo, le dará (una vez que se hayan corregido los errores mencionados anteriormente) una matriz con un elemento, que es claramente incorrecto.
Tim Down
1
@Tim Down: corrigió los errores de sintaxis que señaló. Si es correcto o incorrecto considerar cualquier cosa, ni mucho menos ni menos igual, depende de los requisitos. No noto nada en la pregunta original que diga que se espera que el contenido contenga matrices. Ahora, tiene razón al decir que se debe manejar una entrada inesperada, pero si la especificación ya dicta que esa entrada debe ser una matriz de números (como supuse), entonces el código estaría bien.
atk
1
@atk: Entiendo su punto, ya que el ejemplo en la pregunta usa matrices que solo contienen números.
Tim Down
44
También puede usar .slice(0)para crear un clon de la matriz intersect_safe, en lugar de rastrear índices.
johnluetke
1
@thesmart: tienes razón, definitivamente hay formas más efectivas de hacerlo. El código, arriba, pretendía ser simple, no rápido :)
atk
59

Si su entorno es compatible con ECMAScript 6 Set , una forma simple y supuestamente eficiente (ver enlace de especificació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);
}

Más corto, pero menos legible (también sin crear la intersección adicional Set):

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

Evitar un nuevo Setde bcada vez:

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

Tenga en cuenta que cuando use conjuntos solo obtendrá valores distintos, por lo tanto se new Set[1,2,3,3].sizeevalúa como 3.

nbarbosa
fuente
1
¿Qué es esta [...setA]sintaxis? ¿Algún tipo especial de operación de JavaScript?
jxramos
1
@jxramos, que es la sintaxis Spread y, en este caso, solo se usa para crear una matriz a partir de los elementos del conjunto. "Array.from (setA)" también funcionaría en este caso, pero como la pregunta pedía "más simple", traté de hacerlo más limpio para leer en esa línea. En ese sentido, creo que el código podría ser más simple, así que actualizaré el fragmento.
nbarbosa
@nbarbosa Tengo curiosidad: ¿por qué "clonaste" la matriz a? #filter no destruye la matriz original, ¿verdad? Se crea una nueva matriz?
bplittle
@bplittle Acabo de crear una matriz del conjunto para eliminar duplicados, de lo contrario, usar la matriz directamente daría como resultado la devolución de duplicados. Por ejemplo, si usara la matriz directamente, la intersección ([1,2,2,4], [2,3]) produciría [2, 2].
nbarbosa
2
¿No se x => new Set(b).has(x)convierte esa función de flecha ben un conjunto cada vez que se ejecuta? Probablemente debería guardar ese conjunto en una variable.
Aran-Fey
39

Usando Underscore.js o lodash.js

_.intersection( [0,345,324] , [1,0,324] )  // gives [0,324]
Sai Ram
fuente
20
Op pidió "libre de bibliotecas".
LinuxDisciple
@LinuxDisciple Mi error por perder eso. Gracias por las notas
Sai Ram
33
En cualquier caso, esta es la lista de Google más importante para esta búsqueda, por lo que es útil tener una respuesta de biblioteca. Gracias.
webnoob
Yo también me alegro de que esto fue publicado. La primera vez que sentí la necesidad de underscore.js. Por lo general, el mapa de JavaScript y las tuberías de reducción hacen el trabajo con elegancia, pero esta vez no.
Sridhar Sarnobat
I <3 Underscore y I <3 Jeremy Ashkenas (su creador), pero aun así recomiendo encarecidamente echar un vistazo a Lodash. Básicamente es una versión superior de Underscore (originalmente era una bifurcación) cuyo único inconveniente es el código fuente súper optimizado (y, por lo tanto, casi ilegible). La gente de Underscore incluso consideró deshacerse de Underscore por completo (y solo decirle a la gente que usara Lodash), pero las personas que se preocupan por la legibilidad del código fuente argumentaron que lo mantenían (en realidad estaba de ese lado, pero desde entonces me he convertido a Lodash). @see github.com/jashkenas/underscore/issues/2182
machineghost
14

Mi contribución en términos de ES6. En general, encuentra la intersección de una matriz con un número indefinido de matrices proporcionadas 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("<pre>" + JSON.stringify(arr.intersect(...arrs)) + "</pre>");

Redu
fuente
Este código se ve muy bien, pero no lo entiendo completamente. Posible explicarlo por favor?
habitual
1
@novembersky Reúne todas las matrices de temas en una matriz como [[0,1,2,3,4,5,6,7,8,9],[0,2,4,6,8],[4,5,6,7],[4,6]]y luego se aplica .reduce(). [0,1,2,3,4,5,6,7,8,9].filter( e => [0,2,4,6,8].includes(e)Se realiza la primera operación y el resultado se convierte en nuevo py se cconvierte [4,5,6,7]en el siguiente turno y continúa así hasta que no cquede más.
Reducido el
1
Esta es una solución costosa si está trabajando con grandes conjuntos de datos.
Madbreaks
1
No modifiques prototypeinnecesariamente.
fregante
14

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

Recomiendo una solución sucinta que supera a otras implementaciones en entradas grandes. Si el rendimiento en entradas pequeñas es importante, verifique las alternativas a continuación.

Alternativas y comparación de rendimiento:

Consulte el siguiente fragmento para ver implementaciones alternativas y consulte https://jsperf.com/array-intersection-comparison para ver las comparaciones de rendimiento.

Resultados en Firefox 53:

  • Ops / seg en matrices grandes (10,000 elementos):

    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 / seg en matrices pequeñas (100 elementos):

    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
fuente
2
intersect([1,2,2,3], [2,3,4,5])vuelve [2, 2, 3].
SeregPie
1
@SeregPie Exactamente. Según el comentario "Devolver elementos de la matriz a que también están en b"
le_m
Respuesta de calidad, sin embargo, el uso de Conjuntos altera fundamentalmente los resultados, ya que la pregunta de op solo se refería a las intersecciones de matriz y no menciona / estipula cómo manejar los duplicados. Tímido de eso, esta respuesta puede producir resultados inesperados cuando existen duplicados.
Madbreaks
1
Me encanta, pero has agregado una función innecesaria con "filtro + incluye". tratar a.filter(b.includes). Debería ejecutarse considerablemente más rápido (igual que la actualización de su función).
SEoF
11

¿Qué tal si solo usamos matrices asociativas?

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;
}
Steven Huwig
fuente
1
Esto solo tiene una posibilidad si sus matrices solo contienen cadenas o números, y si ninguna de las secuencias de comandos en su página se ha metido Object.prototype.
Tim Down
2
El ejemplo del OP fue el uso de números, y si un script se ha equivocado con Object.prototype, entonces el script debe reescribirse o eliminarse.
Steven Huwig
No necesita tanto (d1) como (d2). Cree (d2), luego recorra (a) en lugar de recorrer (d1).
StanleyH
Debería ser en d[b[i]] = true;lugar de d[b[j]] = true;( ino j). Pero editar requiere 6 caracteres.
Izhaki
@Izhaki gracias, arreglado. (Se agregó un // comentario para evitar el requisito de edición mínimo.)
Steven Huwig
8
  1. Ordénalo
  2. marque uno por uno del índice 0, cree una nueva matriz a partir de eso.

Algo como esto, aunque no se ha probado bien.

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

PD: El algoritmo solo está destinado a Números y Cadenas normales, la intersección de matrices de objetos arbitrarios puede no funcionar.


fuente
3
La clasificación no necesariamente va a ayudar a las matrices de objetos arbitrarios
Tim abajo
Si la matriz no está ordenada, debe recorrer alrededor de 1,000,000 de veces cuando se cruza con una matriz de 1000 longitudes x una matriz de 1000 longitudes
USTED es el
Creo que te perdiste mi punto, que es que los objetos arbitrarios en JavaScript no tienen un orden de clasificación natural, lo que significa que ordenar una matriz de objetos arbitrarios no dará como resultado la agrupación de objetos iguales. No es bueno tener un algoritmo eficiente que no funciona.
Tim Down
Ah lo siento, me perdí "objetos arbitrarios", sí, tienes razón. esos objetos no pueden ordenarlo, y el algoritmo puede no funcionar en ellos.
USTED
8

El rendimiento de la implementación de @ atk para matrices ordenadas de primitivas se puede mejorar utilizando .pop en lugar 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;
}

Creé un punto de referencia usando jsPerf: http://bit.ly/P9FrZK . Es aproximadamente tres veces más rápido usar .pop.

xn.
fuente
1
Solo como una nota al margen para otros, esto solo funcionará para números, no cadenas.
Izhaki
Tenga en cuenta que si reemplaza a[aLast] > b[bLast]con a[aLast].localeCompare(b[bLast]) > 0(y lo mismo con el else ifsiguiente), esto funcionará en cadenas.
Andrew
1
La diferencia de velocidad depende del tamaño de las matrices porque .popes O (1) y .shift()es O (n)
Esailija
8

Usando jQuery :

var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);
Gowsikan
fuente
8
Esto también podría escribirse como c = $(b).filter(a);, pero no recomendaría confiar en jQuery para este tipo de manipulación de matriz ya que la documentación solo menciona que funciona para elementos.
Stryner
1
Esto no responde la pregunta de op: "¿Cuál es el código más simple y libre de bibliotecas ..."
Madbreaks
7

Para las matrices que contienen solo cadenas o números, puede hacer algo con la clasificación, según algunas de las otras respuestas. Para el caso general de matrices de objetos arbitrarios, no creo que puedas evitar hacerlo a la larga. Lo siguiente le dará la intersección de cualquier número de matrices proporcionadas 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"]; 
Tim Down
fuente
Esto solo funciona en el caso en que la identidad del objeto es la única forma de igualdad.
Steven Huwig
Bueno, sí, pero creo que eso es lo que parece natural para la mayoría de las personas. También es trivial conectar una función alternativa para realizar una prueba de igualdad diferente.
Tim Down
Creo que accidentalmente está creando una variable global firstArr en su ejemplo.
Jason Jackson
@JasonJackson: Tienes razón, gracias. Claramente cambié de opinión sobre si llamar a la variable firstArro firstArrayno actualicé todas las referencias. Fijo.
Tim Down
7

Es bastante corto usando ES2015 y Sets. Acepta valores de tipo matriz como una cadena y elimina duplicados.

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

SeregPie
fuente
Convertir de Set a array con [... a] eliminará los elementos duplicados, buena idea, gracias
V-SHY
1
Esta solución se proporcionó dos veces antes que la suya.
Madbreaks
7

Se puede usar un Setcomo thisArgde Array#filtery tomar Set#hascomo devolución de llamada.

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

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

Nina Scholz
fuente
No sé por qué esto no tiene más votos. Es claramente la mejor respuesta.
Paul Rooney
5

Un pequeño ajuste al más pequeño aquí (la solución filter / indexOf ), es decir, crear un índice de los valores en una de las matrices usando un objeto JavaScript, lo reducirá de O (N * M) a "probablemente" tiempo lineal. 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 no es la solución más simple (es más código que filter + indexOf ), ni es la más rápida (probablemente más lenta por un factor constante que intersect_safe () ), pero parece un buen balance. Es del lado muy simple, a la vez que proporciona un buen rendimiento, y no requiere entradas ordenadas previamente.

David
fuente
5

Otro enfoque indexado capaz de procesar cualquier cantidad de matrices a la 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;
};

Funciona solo para valores que pueden evaluarse como cadenas y debe pasarlos como una matriz como:

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

... pero acepta objetos de forma transparente como parámetro o como cualquiera de los elementos que se van a intersectar (siempre devuelve una matriz de valores comunes). Ejemplos:

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

EDITAR: Acabo de notar que esto es, en cierto modo, un poco defectuoso.

Es decir: lo codifiqué pensando que las matrices de entrada por sí mismas no pueden contener repeticiones (como el ejemplo provisto no lo hace).

Pero si las matrices de entrada contienen repeticiones, eso produciría resultados incorrectos. Ejemplo (usando la implementación a continuación):

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

Afortunadamente, esto es fácil de solucionar simplemente agregando indexación de segundo nivel. Es decir:

Cambio:

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

por:

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

...y:

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

por:

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

Ejemplo 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' ]
bitifet
fuente
2
Esta es la mejor respuesta con una pequeña modificación. Después de la var v = línea agregue if (typeof v == 'function') continue;y omitirá agregar funciones a los resultados. ¡Gracias!
Zsolti
Gracias @Zsolti. No agrego su sugerencia porque tener funciones (y la forma en que queremos manejarlo) está fuera del alcance de la pregunta original. Pero vea mi edición: si puede tener repeticiones en sus matrices de entrada, entonces la implementación original es defectuosa. Lo arreglé en mi edición. ... Por otro lado, si sabe con certeza que no habrá repetición, la implementación original es un poco más barata.
bitifet
... sobre las funciones, también se pueden intersectar: ​​si las detectamos como dice @Zsolti (con if (typeof v == 'function'), entonces podemos usar su stringificación ( v.toString()) como clave para el índice. Pero, debemos hacer algo para preservarlo intacto. forma más fácil de hacerlo es simplemente asignar la función original como valor en lugar de una simple verdadero valor booleano Pero, en ese caso, la última deindexaton debe también alteró para detectar esta condición y restaurar el valor de la derecha (la función)..
bitifet
¿Qué tan rápido puede ser esto con 30 matrices con 100 elementos? ¿Cómo es el uso de la CPU?
aidonsnous
5

Puede usar (para todos los navegadores excepto IE):

const intersection = array1.filter(element => array2.includes(element));

o para IE:

const intersection = array1.filter(element => array2.indexOf(element) !== -1);
jota3
fuente
Sería bueno si pudieras convertir eso en una función
avalanche1
@ avalanche1 const intersection = (a1, a2) => a1.filter (e => a2.incluye (e));
jota3
4
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;
}
Gabe
fuente
4

Con algunas restricciones en sus datos, puede hacerlo en forma lineal. tiempo !

Para enteros positivos : utilice una matriz que asigne los valores a un booleano "visto / no 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;
}

Existe una técnica similar para los objetos : tome una clave ficticia, configúrela como "verdadera" para cada elemento de la matriz1, luego busque esta clave en los elementos de la matriz2. Limpia cuando hayas terminado.

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

Por supuesto, debes asegurarte de que la clave no apareció antes, de lo contrario estarás destruyendo tus datos ...

tarulen
fuente
Por cierto, esto se puede extender fácilmente para interesar cualquier número de matrices: reemplace el booleano por enteros e incremente cada vez que se vea: puede leer fácilmente la intersección en la última ronda.
tarulen
Solución interesante, me gusta. La mayoría de las otras soluciones son O (n ^ 2), pero esto es O (n). Agregué el código entero al violín de rendimiento de ericP aquí jsfiddle.net/321juyLu/2 . Llegó tercero, me gusta :)
rmcsharry
3

Contribuiré con lo que me ha funcionado mejor:

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;
};
}
Johan
fuente
3

"indexOf" para IE 9.0, 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]
Martin Roberto Mondragon Sotel
fuente
2

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

Vlad Bezden
fuente
2

Un enfoque funcional con ES2015

Un enfoque funcional debe considerar el uso de funciones puras sin efectos secundarios, cada uno de los cuales solo tiene que ver con un solo trabajo.

Estas restricciones mejoran la componibilidad y la reutilización de las funciones involucradas.

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

Tenga en cuenta que el nativo Set se utiliza el tipo , que tiene un rendimiento de búsqueda ventajoso.

Evitar duplicados

Obviamente, los elementos que ocurren repetidamente del primero Arrayse conservan, mientras que el segundo Arrayse desduplica. Este puede ser o no el comportamiento deseado. Si necesita un resultado único, simplemente aplique dedupeel primer argumento:

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

Calcule la intersección de cualquier número de Array s

Si desea calcular la intersección de un número arbitrario de Arrays simplemente componga intersectcon foldl. Aquí hay una función de conveniencia:

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


fuente
Impresionantemente funcional: tuve que hacer una doble toma para confirmar que no es Haskell. El único inconveniente es: (expr ? true : false)es redundante. Úselo solo exprsi no se necesitan booleanos reales, solo verdadero / falso.
jose_castro_arnaud
2

Por simplicidad:

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

Beneficios:

  • suciedad simple
  • centrado en datos
  • funciona para un número arbitrario de listas
  • funciona para longitudes arbitrarias de listas
  • funciona para tipos de valores arbitrarios
  • funciona para un orden de clasificación arbitrario
  • conserva la forma (orden de la primera aparición en cualquier matriz)
  • sale temprano donde sea posible
  • memoria segura, sin alterar los prototipos de función / matriz

Inconvenientes:

  • mayor uso de memoria
  • mayor uso de CPU
  • requiere una comprensión de reducir
  • requiere comprensión del flujo de datos

No querrás usar esto para el motor 3D o el trabajo del kernel, pero si tienes problemas para que esto se ejecute en una aplicación basada en eventos, tu diseño tiene problemas más grandes.

Norguard
fuente
2

.reducepara construir un mapa y .filterencontrar la intersección. deletedentro de .filternos permite tratar la segunda matriz como si fuera un 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;
  });
}

Me parece bastante fácil razonar sobre este enfoque. Se realiza en tiempo constante.

Belden
fuente
2

Este es probablemente el más simple, además 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<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"]

Chris Lwin
fuente
esto tiene una complejidad de tiempo O (nm) ... esto podría resolverse en O (n + m)
alchuang
2

Si necesita que maneje la intersección de múltiples matrices:

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]

Belfordz
fuente
Pero, ¿qué tan rápida es esta solución para 30 matrices con 100 elementos?
aidonsnous
Esto no está utilizando más que métodos nativos de Javascript, y por lo tanto, la VM en la que se ejecutará el código es libre de optimizarlo tanto como sea posible. Estoy bastante seguro de que no existe una solución más rápida dado que está ejecutando esto en una versión moderna de V8 en relación con la edad de este comentario.
Belfordz
2

Estilo ES6 de forma sencilla.

const intersection = (a, b) => {
  const s = new Set(b);
  return a.filter(x => s.has(x));
};

Ejemplo:

intersection([1, 2, 3], [4, 3, 2]); // [2, 3]
Mikhail Gorelyshev
fuente
2

He escrito una función de intersección que incluso puede detectar la intersección de una matriz de objetos en función de la propiedad particular de esos objetos.

Por ejemplo,

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

y queremos intersección basada en la idpropiedad, entonces la salida debería ser:

[{id: 20}]

Como tal, la función para el mismo (nota: código ES6) es:

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

y puedes llamar a la función como:

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

También tenga en cuenta: esta función encuentra la intersección considerando que la primera matriz es la matriz primaria y, por lo tanto, el resultado de la intersección será el de la matriz primaria.

Mridul Meharia
fuente
2

Piense que esto será más rápido con el tiempo O (array1 + array2) suponiendo que map.has () es ~ O (1). Corríjame si está equivocado.

const intersection = (a1, a2) => {
  let map = new Map();
  let result = []
  for (let i of a1) {
    if (!map.has(i)) map.set(i, true);
  }
  for (let i of a2) {
    if (map.has(i)) result.push(i)
  }
  return result;
}

ajaix
fuente
1

Aquí está la implementación de 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;
};

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

dorio
fuente
No es una mala referencia si está disponible
undesrcore