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

Presumo que você esteja comparando uma matriz normal. Caso contrário, você precisará 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"));

Uma solução melhor, se você não se importa com a compatibilidade com versões anteriores, está usando o filtro. Mas ainda assim, esta solução funciona.

Existe uma maneira melhor de usar o ES7:

Interseção

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

Pois [1,2,3] [2,3]isso cederá [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));

Pois [1,2,3] [2,3]isso cederá [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)));

Dessa forma, você obterá uma matriz contendo todos os elementos de arr1 que não estão em arr2 e vice-versa

Como @Joshaven Potter apontou em sua resposta, você pode adicioná-lo ao Array.prototype para que ele possa ser usado assim:

Array.prototype.diff = function(arr2) { return this.filter(x => !arr2.includes(x)); }
[1, 2, 3].diff([2, 3])

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

Nota indexOf e filter não estão disponíveis em ie antes de ie9.

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

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

diffagora contém o que estava em old_arrayque não está emnew_array

O método da diferença no Underscore (ou seu substituto drop-in, 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 em qualquer função Underscore, você também pode usá-la em um estilo mais orientado a objetos:

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

JavaScript simples

Existem duas possíveis interpretações para "diferença". Vou deixar você escolher qual você quer. Digamos que você tenha:

var a1 = ['a', 'b'     ];
var a2 = [     'b', 'c'];

1. Se você deseja obter ['a'], use esta função:

   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 um a1 ou a2, mas não ambos - a chamada diferença simétrica ), use esta função:

   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, poderá usar _.difference(a1, a2)(caso 1 acima) ou_.xor(a1, a2) (caso 2).

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

Conjunto ES6, para matrizes muito grandes

O código acima funciona em todos os navegadores. No entanto, para grandes matrizes com mais de 10.000 itens, torna-se bastante lento, porque possui complexidade de O (n²). Em muitos navegadores modernos, podemos tirar proveito do Setobjeto ES6 para acelerar as coisas. O Lodash usa automaticamente Setquando 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.)

Para obter a diferença simétrica, você precisa comparar as matrizes de ambas as formas (ou de todas as formas no caso de várias matrizes)

ES7 (ECMAScript 2016)

// diff between just two arrays:
function arrayDiff(a, b) {
    return [
        ...a.filter(x => !b.includes(x)),
        ...b.filter(x => !a.includes(x))
    ];
}

// diff between multiple arrays:
function arrayDiff(...arrays) {
    return [].concat(...arrays.map( (arr, i) => {
        const others = arrays.slice(0);
        others.splice(i, 1);
        const unique = [...new Set([].concat(...others))];
        return arr.filter(x => !unique.includes(x));
    }));
}

ES6 (ECMAScript 2015)

// diff between just two arrays:
function arrayDiff(a, b) {
    return [
        ...a.filter(x => b.indexOf(x) === -1),
        ...b.filter(x => a.indexOf(x) === -1)
    ];
}

// diff between multiple arrays:
function arrayDiff(...arrays) {
    return [].concat(...arrays.map( (arr, i) => {
        const others = arrays.slice(0);
        others.splice(i, 1);
        const unique = [...new Set([].concat(...others))];
        return arr.filter(x => unique.indexOf(x) === -1);
    }));
}

ES5 (ECMAScript 5.1)

// diff between just two arrays:
function arrayDiff(a, b) {
    var arrays = Array.prototype.slice.call(arguments);
    var diff = [];

    arrays.forEach(function(arr, i) {
        var other = i === 1 ? a : b;
        arr.forEach(function(x) {
            if (other.indexOf(x) === -1) {
                diff.push(x);
            }
        });
    })

    return diff;
}

// diff between multiple arrays:
function arrayDiff() {
    var arrays = Array.prototype.slice.call(arguments);
    var diff = [];

    arrays.forEach(function(arr, i) {
        var others = arrays.slice(0);
        others.splice(i, 1);
        var otherValues = Array.prototype.concat.apply([], others);
        var unique = otherValues.filter(function (x, j) { 
            return otherValues.indexOf(x) === j; 
        });
        diff = diff.concat(arr.filter(x => unique.indexOf(x) === -1));
    });
    return diff;
}

Exemplo:

// diff between two arrays:
const a = ['a', 'd', 'e'];
const b = ['a', 'b', 'c', 'd'];
arrayDiff(a, b); // (3) ["e", "b", "c"]

// diff between multiple arrays
const a = ['b', 'c', 'd', 'e', 'g'];
const b = ['a', 'b'];
const c = ['a', 'e', 'f'];
arrayDiff(a, b, c); // (4) ["c", "d", "g", "f"]

Diferença entre matrizes de objetos

function arrayDiffByKey(key, ...arrays) {
    return [].concat(...arrays.map( (arr, i) => {
        const others = arrays.slice(0);
        others.splice(i, 1);
        const unique = [...new Set([].concat(...others))];
        return arr.filter( x =>
            !unique.some(y => x[key] === y[key])
        );
    }));
}

Exemplo:

const a = [{k:1}, {k:2}, {k:3}];
const b = [{k:1}, {k:4}, {k:5}, {k:6}];
const c = [{k:3}, {k:5}, {k:7}];
arrayDiffByKey('k', a, b, c); // (4) [{k:2}, {k:4}, {k:6}, {k:7}]

Uma abordagem mais limpa no ES6 é a seguinte solução.

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

Diferença

a2.filter(d => !a1.includes(d)) // gives ["c", "d"]

Interseção

a2.filter(d => a1.includes(d)) // gives ["a", "b"]

União disjuntiva (diferença simétrica)

[ ...a2.filter(d => !a1.includes(d)),
  ...a1.filter(d => !a2.includes(d)) ]

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

Verifique se ele se aplica ao seu caso, pois ele 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 as duas matrizes, os valores exclusivos aparecerão apenas uma vez, para que indexOf () seja o mesmo que lastIndexOf ().

para subtrair uma matriz de outra, basta usar o snippet 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 o exemplo de 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;
});

Com a chegada do ES6 com sets e operador splat (no momento em que funciona apenas no Firefox, verifique a tabela de compatibilidade ), é possível 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)))];

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

Abordagem funcional com o ES2015

Computar as differenceduas matrizes é uma das Setoperações. O termo já indica que o Settipo nativo deve ser usado, para aumentar a velocidade da pesquisa. De qualquer forma, existem três permutações ao calcular 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.

Esquerda difference:

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

Direita difference:

differenceré trivial. É apenas differencelcom argumentos invertidos. Você pode escrever uma função por conveniência:const differencer = flip(differencel) . Isso é tudo!

Simétrico difference:

Agora que temos a esquerda e a direita, a implementação da simétrica também differenceé trivial:

// small, reusable auxiliary functions

const apply = f => x => f(x);
const flip = f => y => x => f(x) (y);
const concat = y => xs => xs.concat(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);
};


// symmetric difference

const difference = ys => xs =>
 concat(differencel(xs) (ys)) (flip(differencel) (xs) (ys));

// 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( difference(xs) (ys) );

Acho que este exemplo é um bom ponto de partida para obter uma impressão do que significa programação funcional:

Programação com blocos de construção que podem ser conectados de várias maneiras diferentes.

Uma solução usando indexOf()será boa para pequenas matrizes, mas à medida que elas crescem, o desempenho do algoritmo se aproxima O(n^2). Aqui está uma solução que terá melhor desempenho para matrizes muito grandes usando objetos como matrizes associativas para armazenar as entradas da matriz como chaves; ele também elimina entradas duplicadas automaticamente, mas funciona apenas 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<len; i++) { o1[a1[i]] = true; }
  for (i=0, len=a2.length; i<len; i++) { o2[a2[i]] = true; }
  for (k in o1) { if (!(k in o2)) { diff.push(k); } }
  for (k in o2) { if (!(k in o1)) { diff.push(k); } }
  return diff;
}

var a1 = ['a', 'b'];
var a2 = ['a', 'b', 'c', 'd'];
arrayDiff(a1, a2); // => ['c', 'd']
arrayDiff(a2, a1); // => ['c', 'd']

A resposta acima de Joshaven Potter é ótima. Mas ele 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]);for exibido: ==> [1,2,6], mas não [1,2,6,7] , qual é a diferença real entre os dois. Você ainda pode usar o código de Potter acima, mas simplesmente refazer a comparação uma vez para trás 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 gerar: [ 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]

Além disso, você pode usar a sintaxe da função de seta:

const diffArray = (arr1, arr2) => arr1.concat(arr2)
    .filter(val => !(arr1.includes(val) && arr2.includes(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 função 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<this.length; i++)
    if (this[i] == needle) return true;

  return false;
} 

Array.prototype.diff = function(compare) {
    return this.filter(function(elem) {return !compare.contains(elem);})
}

var a = new Array(1,4,7, 9);
var b = new Array(4, 8, 7);
alert(a.diff(b));

Dessa forma, você pode fazer isso array1.diff(array2)para obter a diferença (no entanto, a complexidade do tempo para o algoritmo é horrível - O (array1.length x array2.length) eu acredito)

Usando 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"]

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

• Solução JavaScript pura (sem bibliotecas)
• Compatível com navegadores mais antigos (não usa filter)
• O (n ^ 2)
• fnParâmetro de retorno de chamada opcional que permite especificar como comparar itens da 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 mescle as duas matrizes, procure as duplicatas e envie o que não é duplicado para 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<arr.length; j++){
      if(arr[j] === f){
        t++; 
        }
    }
    if (t === 1){
      newArr.push(f);
        }
  } 
  return newArr;
}

// abordagem es6

function diff(a, b) {
  var u = a.slice(); //dup the array
  b.map(e => {
    if (u.indexOf(e) > -1) delete u[u.indexOf(e)]
    else u.push(e)   //add non existing item to temp array
  })
  return u.filter((x) => {return (x != null)}) //flatten result
}

Complexidade simétrica e linear . Requer ES6.

function arrDiff(arr1, arr2) {
    var arrays = [arr1, arr2].sort((a, b) => a.length - b.length);
    var smallSet = new Set(arrays[0]);

    return arrays[1].filter(x => !smallSet.has(x));
}

mais uma resposta, mas parece que ninguém mencionou o jsperf, onde eles comparam vários algoritmos e suporte de tecnologia: https://jsperf.com/array-difference-javascript parece que usar filtro obtém os melhores resultados. obrigado

Apenas pensando ... por uma questão de desafio ;-) 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<bigArray.length;i++){
    key = bigArray[i];
    test[key] = true;
  }
  if(!returnUnion){
    //diffing
    for(var i=0;i<smallArray.length;i++){
      key = smallArray[i];
      if(!test[key]){
        test[key] = null;
      }
    }
  } else {
    //union
    for(var i=0;i<smallArray.length;i++){
      key = smallArray[i];
      if(!test[key]){
        test[key] = true;
      }
    }
  }
  for(var i in test){
    ret.push(i);
  }
  return ret;
}

array1 = "test1", "test2","test3", "test4", "test7"
array2 = "test1", "test2","test3","test4", "test5", "test6"
diffArray = diffArrays(array1, array2);
//returns ["test5","test6","test7"]

diffArray = diffArrays(array1, array2, true);
//returns ["test1", "test2","test3","test4", "test5", "test6","test7"]

Observe que a classificação provavelmente não será como observada acima ... mas, se desejar, chame .sort () na matriz para classificá-la.

Eu queria uma função semelhante que incluísse uma matriz antiga e uma nova matriz e me desse uma matriz de itens adicionados e uma matriz de itens removidos, e queria que fosse eficiente (portanto, não contém.).

Você pode brincar com 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 uma resposta simples que não envolvesse o uso de bibliotecas diferentes e criei uma que não acho que tenha sido mencionada aqui. Não sei o quão eficiente é nem nada, 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, também preciso duplicar, mas acho que isso nem sempre é preferido.

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

littlebit correção para a melhor resposta

function arr_diff(a1, a2)
{
  var a=[], diff=[];
  for(var i=0;i<a1.length;i++)
    a[a1[i]]=a1[i];
  for(var i=0;i<a2.length;i++)
    if(a[a2[i]]) delete a[a2[i]];
    else a[a2[i]]=a2[i];
  for(var k in a)
   diff.push(a[k]);
  return diff;
}

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