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

610

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

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

e pegue

[2, 3]
Pedro
fonte
16
Você quer simples ou rápido?
SLaks
11
Prioridade é simples, mas não pode ser tão morte cerebral que vai ser um devorador de desempenho :)
Peter
4
Eu fiz uma página de teste do JsFiddle Banchmark para todos os métodos aqui, incluindo afunção de interseção _underscore . (quanto maior, melhor) ! insira a descrição da imagem aqui Até agora intersect_safe obteve os melhores resultados . VOCÊ & Sublinha o pior.
precisa saber é
Adicionando um breakpara Simple js loopsaumenta os ops / seg para ~ 10M
Richard
19
No caso de você perdê-la : a resposta mais simples não é o único aceito, mas a do fundo: stackoverflow.com/questions/1885557/...
redben

Respostas:

1080

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

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

Ou, como vrugtehagel sugeriu nos comentários, você pode usar o mais recente Array.prototype.includespara um código ainda mais simples:

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

Para navegadores mais antigos:

array1.filter(function(n) {
    return array2.indexOf(n) !== -1;
});
Anon.
fonte
9
Que você pode resolver adicionando uma versão da biblioteca no protótipo da matriz.
Anon.
12
Sim, mas valeu a pena mencionar.
Tim Baixo
18
Melhor resposta aqui, tanto pela simplicidade e trabalhar com os não-números
Muhd
41
intersection([1,2,1,1,3], [1])retorna [1, 1, 1]. Não deveria retornar apenas [1]?
edjroot
21
Em vez de array2.indexOf(n) != -1um também pode escrever array2.includes(n)para um código ainda mais simples.
vrugtehagel
157

Destrutivo parece mais simples, especialmente se pudermos assumir que a entrada está classificada:

/* 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 deve ser um cabelo mais complicado, pois precisamos 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
fonte
14
Existem inúmeros erros em intersect_safe: lengthé uma propriedade em Arrays, não um método. Há uma variável não danificada iem result.push(a[i]);. Finalmente, isso simplesmente não funciona no caso geral: dois objetos em que nenhum é maior que o outro de acordo com o >operador não são necessariamente iguais. intersect_safe( [ {} ], [ {} ] ), por exemplo, fornecerá (assim que os erros mencionados anteriormente forem corrigidos) uma matriz com um elemento, o que está claramente errado.
Tim Baixo
1
@ Tim Down: Corrigidos os erros de sintaxe que você apontou. Se é correto ou incorreto considerar que nem algo nem menos é igual depende dos requisitos. Não percebo nada na pergunta original dizendo que o conteúdo deve conter matrizes. Agora, você diria que a entrada inesperada deve ser manipulada, mas se a especificação já ditar essa entrada deve ser uma matriz de números (como eu assumi), então o código ficaria bem.
Atk
1
@ atk: Entendo o seu ponto, visto que o exemplo na pergunta usa matrizes que contêm apenas números.
Tim Baixo
4
Você também pode usar .slice(0)para criar um clone da matriz intersect_safe, em vez de rastrear índices.
johnluetke
1
@ thesmart: você está certo, existem definitivamente maneiras mais eficientes de fazer isso. O código, acima, tinha a intenção de ser simples, não rápido :) #
atk
59

Se o seu ambiente suportar o ECMAScript 6 Set , uma maneira simples e supostamente eficiente (consulte 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 a interseção adicional Set):

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

Evitando um novo Setde bcada vez:

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

Observe que, ao usar conjuntos, você obterá apenas valores distintos, sendo new Set[1,2,3,3].sizeavaliado como 3.

nbarbosa
fonte
1
qual é essa [...setA]sintaxe? Algum tipo especial de operação javascript?
jxramos
1
@jxramos que é a sintaxe Spread e, neste caso, está sendo usado apenas para criar uma matriz a partir dos elementos no conjunto. "Array.from (setA)" também funcionaria nesse caso, mas, como a pergunta era "mais simples", tentei torná-lo mais limpo para ler nessa linha. Sobre esse assunto, acho que o código poderia ser mais simples, então atualizarei o snippet.
Nbbbosa
@ nbarbosa Estou curioso: por que você "clonou" a matriz a? #filter não destrói a matriz original, certo? Cria uma nova matriz?
bplittle
@bplittle Acabei de criar uma matriz do conjunto para remover duplicatas; caso contrário, usar a matriz diretamente resultaria no retorno de duplicatas. Por exemplo, se eu usasse a matriz diretamente, a interseção ([1,2,2,4], [2,3]) produziria [2, 2].
Nbbbosa
2
Essa x => new Set(b).has(x)função de seta não se transforma bem um conjunto toda vez que é executada? Você provavelmente deve salvar esse conjunto em uma variável.
Aran-Fey
39

Usando Underscore.js ou lodash.js

_.intersection( [0,345,324] , [1,0,324] )  // gives [0,324]
Sai Ram
fonte
20
Op pediu "sem biblioteca".
LinuxDisciple
@LinuxDisciple Meu erro para that.Thanks faltando para notas
Sai Ram
33
De qualquer forma, esta é a lista do Google mais importante para esta pesquisa, portanto, é útil ter uma resposta da biblioteca. Obrigado.
Webnoob 18/01/19
Também estou feliz que isso foi publicado. Primeira vez que senti a necessidade de underscore.js. Normalmente, o mapa JavaScript e os pipelines reduzidos realizam o trabalho com elegância, mas não desta vez.
Sridhar Sarnobat 8/11
Eu <3 Underscore e eu <3 Jeremy Ashkenas (seu criador), mas mesmo assim eu recomendo que você verifique o Lodash. É basicamente uma versão superior do Underscore (originalmente um fork) cuja única desvantagem é o código-fonte super-otimizado (e, portanto, quase ilegível). O pessoal do Underscore até considerou se livrar completamente do Underscore (e apenas dizer para as pessoas usarem o Lodash), mas as pessoas que se preocupam com a legibilidade do código-fonte argumentaram para mantê-lo (eu estava nesse lado, na verdade, mas desde então me converti no Lodash). @see github.com/jashkenas/underscore/issues/2182
machineghost
14

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

Redu
fonte
esse código parece ótimo, mas eu não o entendo completamente. Possível explicar por favor?
theusual
1
@novembersky Reúne todas as matrizes de assuntos em uma matriz como [[0,1,2,3,4,5,6,7,8,9],[0,2,4,6,8],[4,5,6,7],[4,6]]e depois se aplica .reduce(). A primeira [0,1,2,3,4,5,6,7,8,9].filter( e => [0,2,4,6,8].includes(e)operação é executada e o resultado torna-se novo pe ctorna - se [4,5,6,7]no próximo turno e continua assim até que não resta mais c.
Redu
1
Essa é uma solução cara se você estiver trabalhando com grandes conjuntos de dados.
Madbreaks
1
Não modifique o prototypedesnecessariamente.
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]));

Eu recomendo a solução sucinta acima, que supera outras implementações em entradas grandes. Se o desempenho em pequenas entradas for importante, verifique as alternativas abaixo.

Alternativas e comparação de desempenho:

Consulte o seguinte snippet para implementações alternativas e consulte https://jsperf.com/array-intersection-comparison para obter comparações de desempenho.

Resultados no Firefox 53:

  • Ops / s em matrizes 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 / s em pequenas matrizes (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
fonte
2
intersect([1,2,2,3], [2,3,4,5])retorna [2, 2, 3].
SeregPie
1
@SeregPie Exatamente. Como por comentário "elementos de retorno de array a que também estão em b"
le_m
Resposta de qualidade, no entanto, o uso de Sets altera fundamentalmente os resultados, já que a pergunta do op fez apenas sobre interseções de array e não faz nenhuma menção / estipulação de como lidar com duplicatas. Além disso, essa resposta pode gerar resultados inesperados quando existirem duplicatas.
Madbreaks
1
Adorei, mas você adicionou uma função desnecessária com "filtro + inclui". tente a.filter(b.includes). Ele deve executar consideravelmente mais rápido (o mesmo que sua atualização de função).
Seof
11

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;
}
Steven Huwig
fonte
1
Isso só tem chance se suas matrizes contiverem apenas seqüências de caracteres ou números e se nenhum dos scripts da sua página tiver sido afetado Object.prototype.
Tim Baixo
2
O exemplo do OP estava usando números e, se um script alterou o objeto Object.prototype, o script deve ser reescrito ou removido.
9139 Steven Huwig
Você não precisa de ambos (d1) e (d2). Crie (d2) e, em seguida, faça um loop em (a) em vez de em (d1).
StanleyH
Deve ser em d[b[i]] = true;vez de d[b[j]] = true;( inão j). Mas editar requer 6 caracteres.
Izhaki 30/07/12
@ Izhaki obrigado, corrigido. (Adicionado a // comentário de obter exigência torno mínimo de edição.)
Steven Huwig
8
  1. Classificar
  2. verifique um a um no índice 0, crie uma nova matriz a partir disso.

Algo parecido com isto, mas não testado bem.

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: o algoritmo destinado apenas a números e seqüências normais, a interseção de matrizes de objetos arbitrários pode não funcionar.

VOCÊ
fonte
3
Classificando não vai necessariamente ajudar para matrizes de objetos arbitrários
Tim Baixo
Se a matriz não está classificada, necessidade de laço em torno de 1.000.000 vezes quando você se cruzam 1000 comprimento da matriz x 1000 comprimento da matriz
VOCÊ
Acho que você perdeu o meu argumento, que é que objetos arbitrários em JavaScript não têm ordem de classificação natural, o que significa que a classificação de uma matriz de objetos arbitrários não resultará no agrupamento de objetos iguais. Não é bom ter um algoritmo eficiente que não funcione.
Tim Baixo
Desculpe, perdi "objetos arbitrários", sim, você está certo. esses objetos não podem classificá-lo e o algoritmo pode não funcionar com eles.
VOCÊ
8

O desempenho da implementação do @ atk para matrizes classificadas de primitivas pode ser aprimorado 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;
}

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

xn.
fonte
1
Apenas como uma nota lateral para outros - isso funcionará apenas para números, não para strings.
Izhaki 30/07/12
Observe que se você substituir a[aLast] > b[bLast]por a[aLast].localeCompare(b[bLast]) > 0(e o mesmo com o else ifabaixo), isso funcionará em cadeias.
andrew
1
A diferença de velocidade depende do tamanho das matrizes porque .popé O (1) e .shift()é 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
fonte
8
Isso também pode ser escrito como c = $(b).filter(a);, mas eu não recomendaria confiar no jQuery para esse tipo de manipulação de matriz, pois a documentação menciona apenas que funciona para elementos.
Stryner 23/09/15
1
Pergunta deste op não responde: "O que é o mais simples, livre de biblioteca de código ..."
Madbreaks
7

Para matrizes que contêm apenas strings ou números, você pode fazer algo com a classificação, conforme algumas das outras respostas. Para o caso geral de matrizes de objetos arbitrários, não acho que você possa evitar fazê-lo pelo longo caminho. A seguir, será apresentada 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"]; 
Tim Down
fonte
Isso funciona apenas no caso em que a identidade do objeto é a única forma de igualdade.
9139 Steven Huwig
Bem, sim, mas acho que é o que parece natural para a maioria das pessoas. Também é trivial conectar uma função alternativa para executar um teste de igualdade diferente.
Tim Baixo
Eu acho que você acidentalmente está criando uma variável global firstArr no seu exemplo.
Jason Jackson
@ JasonJackson: Você está certo, obrigado. Claramente mudei de idéia sobre chamar firstArrou firstArraynão a variável e não atualizei todas as referências. Fixo.
Tim Baixo
7

É bem curto usando ES2015 e Sets. Aceita valores do tipo Array como uma String 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(''));

SeregPie
fonte
Converter de Set em array com [...] removerá os itens duplicados, boa ideia, obrigado #
4307 V-
1
Esta solução foi fornecida duas vezes antes da sua.
Madbreaks
7

Você pode usar um a Setpartir thisArgde Array#filtere receber Set#hascomo retorno de chamada.

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
fonte
Não sei por que isso não tem mais votos. É claramente a melhor resposta.
Paul Rooney
5

Um pequeno ajuste no menor aqui (a solução filter / indexOf ), ou seja, criar um índice dos valores em uma das matrizes usando um objeto JavaScript, reduzirá 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 é a mais rápida (provavelmente mais lenta por um fator constante do que intersect_safe () ), mas parece ser um bom equilíbrio. É no muito lado simples, oferecendo um bom desempenho, e não requer entradas pré-ordenada.

David
fonte
5

Outra abordagem indexada capaz de processar qualquer número de matrizes de uma 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 apenas para valores que podem ser avaliados como strings e você deve transmiti-los como uma matriz como:

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

... mas aceita objetos de forma transparente como parâmetro ou como qualquer um dos elementos a serem cruzados (sempre retornando uma 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"]

Edição: Acabei de perceber que isso é, de certa forma, um pouco buggy.

Ou seja: eu o codifiquei pensando que matrizes de entrada não podem conter repetições (como o exemplo fornecido não).

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

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

Felizmente, isso é fácil de corrigir, basta adicionar 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' ]
bitifet
fonte
2
Esta é, de longe, a melhor resposta com uma pequena modificação. Após a var v = linha, adicione if (typeof v == 'function') continue;e ela pulará a adição de funções aos resultados. Obrigado!
Zsolti 31/08/16
Obrigado @Zsolti. Não adiciono sua sugestão porque ter funções (e a maneira como queremos lidar com isso) está fora do escopo da pergunta original. Mas veja minha edição: se você pode ter repetições em suas matrizes de entrada, a implementação original é incorreta. Corrigi-o na minha edição. ... Por outro lado, se você tem certeza de que não haverá repetição, a implementação original é um pouco mais barata.
bitifet 6/10/19
... sobre funções, elas também podem ser cruzadas: se as detectarmos como o @Zsolti diz (com if (typeof v == 'function') , poderemos usar sua stringification ( v.toString()) como chave para o índice. Mas precisamos fazer algo para preservá-lo intacto. A maneira mais fácil de fazer isso é simplesmente atribuir a função original como valor, em vez de um simples valor verdadeiro booleano, mas, nesse caso, a mais recente desindexação também deve ser alterada para detectar essa condição e restaurar o valor correto (a função).
bitifet
Quão rápido isso pode ser com 30 matrizes com 100 elementos ... como é o uso da CPU?
aidonsnous
5

Você pode usar (para todos os navegadores, exceto o IE):

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

ou para o IE:

const intersection = array1.filter(element => array2.indexOf(element) !== -1);
jota3
fonte
Seria bom se você pudesse transformar isso em uma função
avalanche1
@ avalanche1 const interseção = (a1, a2) => a1.filter (e => a2.inclui (e));
jota3 17/02
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
fonte
4

Com algumas restrições em seus dados, você pode fazer isso de forma linear tempo !

Para números inteiros positivos : use uma matriz que mapeie 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;
}

Existe uma técnica semelhante para objetos : pegue uma chave fictícia, defina-a como "true" para cada elemento da matriz1 e, em seguida, procure essa chave nos elementos da matriz2. Limpe quando terminar.

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, caso contrário você estará destruindo seus dados ...

tarulen
fonte
A propósito, isso pode ser facilmente estendido para interceptar qualquer número de matrizes: substitua o booleano por números inteiros e aumente cada vez que for visto: você pode ler facilmente a interseção na última rodada.
Tarulen # 5/15
Solução interessante, eu gosto. A maioria das outras soluções é O (n ^ 2), mas é O (n). Adicionei o código inteiro ao violino de desempenho do ericP aqui jsfiddle.net/321juyLu/2 . Ele veio 3, me likey :)
rmcsharry
3

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;
};
}
Johan
fonte
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
fonte
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
fonte
2

Uma abordagem funcional com o ES2015

Uma abordagem funcional deve considerar o uso apenas de funções puras, sem efeitos colaterais, cada uma delas relacionada apenas a um único trabalho.

Essas restrições aprimoram a composibilidade e a 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) );

Observe que o Settipo nativo é usado, com um desempenho de pesquisa vantajoso.

Evite duplicatas

Obviamente, os itens de ocorrência repetida do primeiro Arraysão preservados, enquanto o segundo Arrayé desduplicado. Este pode ser ou não o comportamento desejado. Se você precisar de um resultado exclusivo, basta aplicar dedupeao primeiro 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 a interseção de qualquer número de Array s

Se você deseja calcular a interseção de um número arbitrário de Arrays, basta compor intersectcom foldl. Aqui está uma função de conveniência:

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


fonte
Impressionantemente funcional: teve que fazer uma análise dupla para confirmar que não é Haskell. O único nitpick é: (expr ? true : false)é redundante. Use apenas exprse os booleanos reais não forem necessários, apenas verdade / falsidade.
jose_castro_arnaud
2

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
  • centrado em dados
  • trabalha para um número arbitrário de listas
  • funciona para comprimentos arbitrários de listas
  • trabalha para tipos arbitrários de valores
  • funciona para ordem de classificação arbitrária
  • mantém a forma (ordem da primeira aparição em qualquer matriz)
  • sai cedo sempre que possível
  • memória segura, sem violações dos protótipos de função / matriz

Desvantagens:

  • maior uso de memória
  • maior uso da CPU
  • requer uma compreensão de reduzir
  • requer compreensão do fluxo de dados

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

Norguard
fonte
2

.reducepara construir um mapa e .filterencontrar a interseção. deletedentro do .filterpermite tratar a segunda matriz 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 bastante fácil de raciocinar. Ele executa em tempo constante.

Belden
fonte
2

Este é provavelmente o mais simples, além do 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
fonte
isso tem complexidade de tempo em O (nm) ... isso pode ser resolvido em O (n + m)
alchuang
2

Se você precisar lidar com a interseção de várias matrizes:

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
fonte
Mas qual é a velocidade dessa solução para 30 matrizes com 100 elementos?
aidonsnous
Isso está usando nada além de métodos Javascript nativos e, portanto, a VM na qual o código será executado é livre para otimizá-lo o máximo possível. Tenho certeza de que não existe uma solução mais rápida, pois você está executando isso em uma versão moderna do V8 em relação à idade deste comentário.
Belfordz 28/05/19
2

ES6 estilo maneira simples.

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

Exemplo:

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

Eu escrevi uma função de interseção que pode até detectar interseção de matriz de objetos com base na propriedade particular desses objetos.

Por exemplo,

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

e queremos interseção com base na idpropriedade, a saída deve ser:

[{id: 20}]

Como tal, a função para o mesmo (nota: código ES6) é:

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

e você pode chamar a função como:

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

Observe também: essa função encontra interseção, considerando que a primeira matriz é a matriz primária e, portanto, o resultado da interseção será o da matriz primária.

Mridul Meharia
fonte
2

Acho que isso será mais rápido com o tempo O (array1 + array2) assumindo que map.has () é ~ O (1). Corrija-me se estiver errado.

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
fonte
1

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

Dorian
fonte
Não uma referência ruim se undesrcore está disponível
Dimitrios Mistriotis