Como obter a diferença entre duas matrizes em JavaScript?

Existe uma maneira de retornar a diferença entre duas matrizes em JavaScript?

Por exemplo:

var a1 = ['a', 'b']; var a2 = ['a', 'b', 'c', 'd']; // need ["c", "d"] 

Qualquer conselho muito apreciado.

Eu suponho que você está comparando uma matriz normal. Caso contrário, você precisa alterar o loop for para um loop for .. in .

 function arr_diff (a1, a2) { var a = [], diff = []; for (var i = 0; i < a1.length; i++) { a[a1[i]] = true; } for (var i = 0; i < a2.length; i++) { if (a[a2[i]]) { delete a[a2[i]]; } else { a[a2[i]] = true; } } for (var k in a) { diff.push(k); } return diff; } console.log(arr_diff(['a', 'b'], ['a', 'b', 'c', 'd'])); console.log(arr_diff("abcd", "abcde")); console.log(arr_diff("zxc", "zxc")); 
 Array.prototype.diff = function(a) { return this.filter(function(i) {return a.indexOf(i) < 0;}); }; //////////////////// // Examples //////////////////// [1,2,3,4,5,6].diff( [3,4,5] ); // => [1, 2, 6] ["test1", "test2","test3","test4","test5","test6"].diff(["test1","test2","test3","test4"]); // => ["test5", "test6"] 
 Array.prototype.diff = function(a) { return this.filter(function(i) {return a.indexOf(i) < 0;}); }; //////////////////// // Examples //////////////////// var dif1 = [1,2,3,4,5,6].diff( [3,4,5] ); console.log(dif1); // => [1, 2, 6] var dif2 = ["test1", "test2","test3","test4","test5","test6"].diff(["test1","test2","test3","test4"]); console.log(dif2); // => ["test5", "test6"] 

Existe uma maneira melhor de usar o ES7:

Interseção

  let intersection = arr1.filter(x => arr2.includes(x)); 

Diferença de intersecção Diagrama de Venn

Para [1,2,3] [2,3] produzirá [2,3] . Por outro lado, para [1,2,3] [2,3,5] retornará a mesma coisa.

Diferença

 let difference = arr1.filter(x => !arr2.includes(x)); 

Diagrama de Venn de diferença correta

Para [1,2,3] [2,3] ele produzirá [1] . Por outro lado, para [1,2,3] [2,3,5] retornará a mesma coisa.

Para uma diferença simétrica , você pode fazer:

 let difference = arr1 .filter(x => !arr2.includes(x)) .concat(arr2.filter(x => !arr1.includes(x))); 

Diagrama de Venn de diferença simétrica

Desta forma, você irá obter um array contendo todos os elementos de arr1 que não estão em arr2 e vice-versa

Como @Joshaven Potter apontou sua resposta, você pode adicionar isso ao Array.prototype para que ele possa ser usado assim:

 Array.prototype.diff = arr1.filter(x => arr2.includes(x)); [1, 2, 3].diff([2, 3]) 

Esta é de longe a maneira mais fácil de obter exatamente o resultado que você está procurando, usando jQuery:

 var diff = $(old_array).not(new_array).get(); 

diff agora contém o que estava em old_array que não está em new_array

O método de diferença em Underscore (ou seu substituto, Lo-Dash ) também pode fazer isso:

 (R)eturns the values from array that are not present in the other arrays _.difference([1, 2, 3, 4, 5], [5, 2, 10]); => [1, 3, 4] 

Como com qualquer function Underscore, você também pode usá-lo em um estilo mais orientado a object:

 _([1, 2, 3, 4, 5]).difference([5, 2, 10]); 

JavaScript simples

Existem duas possíveis interpretações para “diferença”. Eu vou deixar você escolher qual deles você quer. Diga que você tem:

 var a1 = ['a', 'b' ]; var a2 = [ 'b', 'c']; 
  1. Se você deseja obter ['a'] , use esta function:

     function difference(a1, a2) { var result = []; for (var i = 0; i < a1.length; i++) { if (a2.indexOf(a1[i]) === -1) { result.push(a1[i]); } } return result; } 
  2. Se você deseja obter ['a', 'c'] (todos os elementos contidos em a1 ou a2 , mas não em ambos - a chamada diferença simétrica ), use esta function:

     function symmetricDifference(a1, a2) { var result = []; for (var i = 0; i < a1.length; i++) { if (a2.indexOf(a1[i]) === -1) { result.push(a1[i]); } } for (i = 0; i < a2.length; i++) { if (a1.indexOf(a2[i]) === -1) { result.push(a2[i]); } } return result; } 

Lodash / sublinhado

Se você estiver usando lodash, você pode usar _.difference(a1, a2) (case 1 acima) ou _.xor(a1, a2) (case 2).

Se você estiver usando Underscore.js, poderá usar a function _.difference(a1, a2) para o caso 1.

ES6 Set, para matrizes muito grandes

O código acima funciona em todos os navegadores. No entanto, para grandes matrizes de mais de 10.000 itens, ela se torna bastante lenta, porque tem complexidade O (n²). Em muitos navegadores modernos, podemos aproveitar o object ES6 Set para acelerar as coisas. O Lodash usa automaticamente o Set quando está disponível. Se você não estiver usando o lodash, use a seguinte implementação, inspirada na postagem do blog de Axel Rauschmayer :

 function difference(a1, a2) { var a2Set = new Set(a2); return a1.filter(function(x) { return !a2Set.has(x); }); } function symmetricDifference(a1, a2) { return difference(a1, a2).concat(difference(a2, a1)); } 

Notas

O comportamento de todos os exemplos pode ser surpreendente ou não óbvio se você se preocupa com -0, +0, NaN ou matrizes esparsas. (Para a maioria dos usos, isso não importa.)

Você poderia usar um conjunto neste caso. É otimizado para este tipo de operação (união, intersecção, diferença).

Certifique-se de que se aplica ao seu caso, uma vez que não permite duplicatas.

 var a = new JS.Set([1,2,3,4,5,6,7,8,9]); var b = new JS.Set([2,4,6,8]); a.difference(b) // -> Set{1,3,5,7,9} 
 function diff(a1, a2) { return a1.concat(a2).filter(function(val, index, arr){ return arr.indexOf(val) === arr.lastIndexOf(val); }); } 

Mesclar ambas as matrizes, valores exclusivos aparecerão apenas uma vez, então indexOf () será o mesmo que lastIndexOf ().

para subtrair um array de outro, basta usar o trecho abaixo:

 var a1 = ['1','2','3','4','6']; var a2 = ['3','4','5']; var items = new Array(); items = jQuery.grep(a1,function (item) { return jQuery.inArray(item, a2) < 0; }); 

Ele retornará ['1,' 2 ',' 6 '] que são itens da primeira matriz que não existem na segunda.

Portanto, de acordo com a amostra do seu problema, o código a seguir é a solução exata:

 var array1 = ["test1", "test2","test3", "test4"]; var array2 = ["test1", "test2","test3","test4", "test5", "test6"]; var _array = new Array(); _array = jQuery.grep(array2, function (item) { return jQuery.inArray(item, array1) < 0; }); 

Uma solução usando indexOf() será ok para matrizes pequenas, mas conforme elas crescem em comprimento, o desempenho do algoritmo se aproxima de O(n^2) . Aqui está uma solução que funcionará melhor para matrizes muito grandes usando objects como matrizes associativas para armazenar as inputs da matriz como chaves; Ele também elimina inputs duplicadas automaticamente, mas só funciona com valores de string (ou valores que podem ser armazenados com segurança como strings):

 function arrayDiff(a1, a2) { var o1={}, o2={}, diff=[], i, len, k; for (i=0, len=a1.length; i ['c', 'd'] arrayDiff(a2, a1); // => ['c', 'd'] 

Com a chegada do ES6 com conjuntos e operador splat (no momento de estar funcionando apenas no Firefox, verifique a tabela de compatibilidade ), você pode escrever o seguinte liner:

 var a = ['a', 'b', 'c', 'd']; var b = ['a', 'b']; var b1 = new Set(b); var difference = [...new Set([...a].filter(x => !b1.has(x)))]; 

que resultará em [ "c", "d" ] .

Abordagem funcional com o ES2015

A computação da difference entre duas matrizes é uma das operações do Set . O termo já indica que o tipo Set nativo deve ser usado para aumentar a velocidade de pesquisa. De qualquer forma, existem três permutações quando você calcula a diferença entre dois conjuntos:

 [+left difference] [-intersection] [-right difference] [-left difference] [-intersection] [+right difference] [+left difference] [-intersection] [+right difference] 

Aqui está uma solução funcional que reflete essas permutações.

difference esquerda:

 // small, reusable auxiliary functions const apply = f => x => f(x); const flip = f => y => x => f(x) (y); const createSet = xs => new Set(xs); const filter = f => xs => xs.filter(apply(f)); // left difference const differencel = xs => ys => { const zs = createSet(ys); return filter(x => zs.has(x) ? false : true ) (xs); }; // mock data const xs = [1,2,2,3,4,5]; const ys = [0,1,2,3,3,3,6,7,8,9]; // run the computation console.log( differencel(xs) (ys) ); 

A resposta acima por Joshaven Potter é ótima. Mas retorna elementos na matriz B que não estão na matriz C, mas não o contrário. Por exemplo, se var a=[1,2,3,4,5,6].diff( [3,4,5,7]); então ele produzirá: ==> [1,2,6] , mas não [1,2,6,7] , que é a diferença real entre os dois. Você ainda pode usar o código do Potter acima, mas simplesmente refazer a comparação uma vez também:

 Array.prototype.diff = function(a) { return this.filter(function(i) {return !(a.indexOf(i) > -1);}); }; //////////////////// // Examples //////////////////// var a=[1,2,3,4,5,6].diff( [3,4,5,7]); var b=[3,4,5,7].diff([1,2,3,4,5,6]); var c=a.concat(b); console.log(c); 

Isso deve resultar: [ 1, 2, 6, 7 ]

Outra maneira de resolver o problema

 function diffArray(arr1, arr2) { return arr1.concat(arr2).filter(function (val) { if (!(arr1.includes(val) && arr2.includes(val))) return val; }); } diffArray([1, 2, 3, 7], [3, 2, 1, 4, 5]); // return [7, 4, 5] 
 Array.prototype.difference = function(e) { return this.filter(function(i) {return e.indexOf(i) < 0;}); }; eg:- [1,2,3,4,5,6,7].difference( [3,4,5] ); => [1, 2, 6 , 7] 

Solução muito simples com a function de filtro do JavaScript:

 var a1 = ['a', 'b']; var a2 = ['a', 'b', 'c', 'd']; function diffArray(arr1, arr2) { var newArr = []; var myArr = arr1.concat(arr2); newArr = myArr.filter(function(item){ return arr2.indexOf(item) < 0 || arr1.indexOf(item) < 0; }); alert(newArr); } diffArray(a1, a2); 

Que tal agora:

 Array.prototype.contains = function(needle){ for (var i=0; i 

Então, desta forma você pode fazer array1.diff(array2) para obter a diferença (complexidade de tempo horrível para o algoritmo embora - O (array1.length x array2.length) eu acredito)

Usando o http://phrogz.net/JS/ArraySetMath.js você pode:

 var array1 = ["test1", "test2","test3", "test4"]; var array2 = ["test1", "test2","test3","test4", "test5", "test6"]; var array3 = array2.subtract( array1 ); // ["test5", "test6"] var array4 = array1.exclusion( array2 ); // ["test5", "test6"] 
  • Solução JavaScript pura (sem bibliotecas)
  • Compatível com navegadores mais antigos (não usa filter )
  • O (n ^ 2)
  • Parâmetro de retorno de chamada fn opcional que permite especificar como comparar itens de matriz
 function diff(a, b, fn){ var max = Math.max(a.length, b.length); d = []; fn = typeof fn === 'function' ? fn : false for(var i=0; i < max; i++){ var ac = i < a.length ? a[i] : undefined bc = i < b.length ? b[i] : undefined; for(var k=0; k < max; k++){ ac = ac === undefined || (k < b.length && (fn ? fn(ac, b[k]) : ac == b[k])) ? undefined : ac; bc = bc === undefined || (k < a.length && (fn ? fn(bc, a[k]) : bc == a[k])) ? undefined : bc; if(ac == undefined && bc == undefined) break; } ac !== undefined && d.push(ac); bc !== undefined && d.push(bc); } return d; } alert( "Test 1: " + diff( [1, 2, 3, 4], [1, 4, 5, 6, 7] ).join(', ') + "\nTest 2: " + diff( [{id:'a',toString:function(){return this.id}},{id:'b',toString:function(){return this.id}},{id:'c',toString:function(){return this.id}},{id:'d',toString:function(){return this.id}}], [{id:'a',toString:function(){return this.id}},{id:'e',toString:function(){return this.id}},{id:'f',toString:function(){return this.id}},{id:'d',toString:function(){return this.id}}], function(a, b){ return a.id == b.id; } ).join(', ') ); 

Isso está funcionando: basicamente mesclar as duas matrizes, procure as duplicatas e empurre o que não é duplicado em uma nova matriz que é a diferença.

 function diff(arr1, arr2) { var newArr = []; var arr = arr1.concat(arr2); for (var i in arr){ var f = arr[i]; var t = 0; for (j=0; j 
 function diffArray(arr1, arr2) { var newArr = arr1.concat(arr2); return newArr.filter(function(i){ return newArr.indexOf(i) == newArr.lastIndexOf(i); }); } 

isso funciona para mim

Apenas pensando … por causa de um desafio 😉 isso funcionaria … (para matrizes básicas de strings, números, etc.) sem matrizes aninhadas

 function diffArrays(arr1, arr2, returnUnion){ var ret = []; var test = {}; var bigArray, smallArray, key; if(arr1.length >= arr2.length){ bigArray = arr1; smallArray = arr2; } else { bigArray = arr2; smallArray = arr1; } for(var i=0;i 

Note que a ordenação provavelmente não será como indicado acima ... mas, se desejar, chame .sort () no array para classificá-lo.

littlebit consertar a melhor resposta

 function arr_diff(a1, a2) { var a=[], diff=[]; for(var i=0;i 

Isso levará em consideração o tipo atual de elemento. b / c quando fazemos um [a1 [i]] ele converte um valor para string de seu valor oroginal, então perdemos o valor real.

Isso foi inspirado na resposta aceita por Thinker, mas a resposta de Thinker parece assumir que os arrays são conjuntos. Ele desmorona se os arrays forem [ "1", "2" ] e [ "1", "1", "2", "2" ]

A diferença entre esses arrays é [ "1", "2" ] . A solução a seguir é O (n * n), portanto, não é ideal, mas se você tiver grandes matrizes, também terá vantagens de memory sobre a solução do Thinker.

Se você está lidando com sets em primeiro lugar, a solução do Thinker é definitivamente melhor. Se você tiver uma versão mais recente do Javascript com access a filtros, deverá usá-los também. Isto é apenas para aqueles que não estão lidando com conjuntos e estão usando uma versão mais antiga do JavaScript (por qualquer motivo) …

 if (!Array.prototype.diff) { Array.prototype.diff = function (array) { // if the other array is a falsy value, return a copy of this array if ((!array) || (!Array.prototype.isPrototypeOf(array))) { return this.slice(0); } var diff = []; var original = this.slice(0); for(var i=0; i < array.length; ++i) { var index = original.indexOf(array[i]); if (index > -1) { original.splice(index, 1); } else { diff.push(array[i]); } } for (var i=0; i < original.length; ++i) { diff.push(original[i]); } return diff; } } 
 function diff(arr1, arr2) { var filteredArr1 = arr1.filter(function(ele) { return arr2.indexOf(ele) == -1; }); var filteredArr2 = arr2.filter(function(ele) { return arr1.indexOf(ele) == -1; }); return filteredArr1.concat(filteredArr2); } diff([1, "calf", 3, "piglet"], [1, "calf", 3, 4]); // Log ["piglet",4] 

Se as matrizes não são de tipos simples, então uma das respostas acima pode ser adaptada:

 Array.prototype.diff = function(a) { return this.filter(function(i) {return a.map(function(e) { return JSON.stringify(e); }).indexOf(JSON.stringify(i)) < 0;}); }; 

Esse método funciona em matrizes de objects complexos.

Eu queria uma function semelhante que recebesse uma matriz antiga e uma nova matriz e me fornecesse uma matriz de itens adicionados e uma matriz de itens removidos, e eu queria que ela fosse eficiente (por isso, não .contains!).

Você pode jogar com a minha solução proposta aqui: http://jsbin.com/osewu3/12 .

Alguém pode ver algum problema / melhoria nesse algoritmo? Obrigado!

Listagem de código:

 function diff(o, n) { // deal with empty lists if (o == undefined) o = []; if (n == undefined) n = []; // sort both arrays (or this won't work) o.sort(); n.sort(); // don't compare if either list is empty if (o.length == 0 || n.length == 0) return {added: n, removed: o}; // declare temporary variables var op = 0; var np = 0; var a = []; var r = []; // compare arrays and add to add or remove lists while (op < o.length && np < n.length) { if (o[op] < n[np]) { // push to diff? r.push(o[op]); op++; } else if (o[op] > n[np]) { // push to diff? a.push(n[np]); np++; } else { op++;np++; } } // add remaining items if( np < n.length ) a = a.concat(n.slice(np, n.length)); if( op < o.length ) r = r.concat(o.slice(op, o.length)); return {added: a, removed: r}; } 

Eu estava procurando por uma resposta simples que não envolvesse o uso de bibliotecas diferentes, e criei as minhas próprias que não acho que tenham sido mencionadas aqui. Eu não sei quão eficiente é ou qualquer coisa, mas funciona;

  function find_diff(arr1, arr2) { diff = []; joined = arr1.concat(arr2); for( i = 0; i < = joined.length; i++ ) { current = joined[i]; if( joined.indexOf(current) == joined.lastIndexOf(current) ) { diff.push(current); } } return diff; } 

Para o meu código eu preciso de duplicatas retiradas também, mas eu acho que nem sempre é o preferido.

Eu acho que a principal desvantagem é potencialmente comparar muitas opções que já foram rejeitadas.

Em resposta à pessoa que queria subtrair um array de outro …

Se não mais do que dizer 1000 elementos tente isso …

Configurar uma nova variável para duplicar Array01 e chamá-lo Array03.

Agora, use o algoritmo de sorting de bolhas para comparar os elementos de Array01 com Array02 e sempre que você encontrar uma correspondência, faça o seguinte para Array03 …

  if (Array01[x]==Array02[y]) {Array03.splice(x,1);} 

NB: Estamos modificando Array03 ao invés de Array01 para não estragar os loops nesteds do tipo bubble!

Finalmente, copie o conteúdo de Array03 para Array01 com uma atribuição simples e pronto.

Você pode usar underscore.js: http://underscorejs.org/#intersection

Você precisou de methods para matriz:

 _.difference([1, 2, 3, 4, 5], [5, 2, 10]); => [1, 3, 4] _.intersection([1, 2, 3], [101, 2, 1, 10], [2, 1]); => [1, 2]