如何在JavaScript中获取两个数组之间的差异?

1333

有没有一种方法可以在 JavaScript 中返回两个数组的差异?

例如:

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

// need ["c", "d"]

16
对称还是非对称? - Lightness Races in Orbit
2
使用新的ES6函数,这可以作为一个简单的一行代码完成(在所有主要浏览器中使用它需要很长时间)。无论如何,请查看我的答案 - Salvador Dali
2
解决方案的一个重要方面是性能。这种类型操作的渐进时间复杂度 - 在其他语言中 - 是 O(a1.length x log(a2.length)) - 这种性能在JavaScript中是否可能? - Raul
请查看我的库,它可以帮助您解决这个问题,@netilon/differify 是用于对象/数组比较的最快速的差异库之一: https://www.npmjs.com/package/@netilon/differify - Fabian Orue
1
  1. 将a1转换为集合。o(a1)。
  2. 迭代e2以查看它具有而e1没有的内容。o(e2)。
  3. 将差异推入另一个数组,然后在完成步骤2后返回它。
- powerup7
您可以使用筛选器,检查我的答案https://dev59.com/aXM_5IYBdhLWcg3w3nbz#74317431 - Manu Rastogi
84个回答

34
function diff(a1, a2) {
  return a1.concat(a2).filter(function(val, index, arr){
    return arr.indexOf(val) === arr.lastIndexOf(val);
  });
}

合并这两个数组,唯一的值只会出现一次,所以indexOf()和lastIndexOf()会返回相同的值。


3
我同意这是最干净、最简单的方法,而且很好的是不需要改动原型。"如果你不能向一个六岁的孩子解释清楚,说明你自己也不理解它。" ——阿尔伯特·爱因斯坦 - lacostenycoder

33

随着ES6的出现,引入了集合和splat操作符(目前仅在Firefox中可用,请查看兼容性表格),您可以编写以下一行代码:

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

这将导致 [ "c", "d" ] 的结果。


只是好奇,这与执行 b.filter(x => !a.indexOf(x)) 有什么不同吗? - chovy
2
@chovy,时间复杂度不同。我的解决方案是O(n + m),而你的解决方案是O(n * m),其中n和m是数组的长度。当处理长列表时,我的解决方案将在几秒钟内运行,而你的则需要数小时。 - Salvador Dali
1
对于比较一个对象列表的属性,这个方案是否可行? - chovy
3
a.filter(x => !b1.has(x)) 更简单。请注意,规范仅要求复杂度为 n * f(m) + m,其中 f(m) 在平均情况下是次线性的。它比 n * m 更好,但不一定比 n + m 好。 - Oriol
3
@SalvadorDali 为什么要创建重复的 'a' 数组?为什么要将过滤器的结果转换为集合,然后再转换回数组?这不等同于 var difference = a.filter(x => !b1.has(x)); 吗? - Deepak Mittal
显示剩余3条评论

17

要从一个数组中减去另一个数组,只需使用以下片段:

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;
});
它将返回 ['1,'2','6'],这些是第一个数组中存在但在第二个数组中不存在的项。
因此,根据您的问题示例,以下代码是确切的解决方案:
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;
});

16

解决问题的另一种方式

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]

同时,你可以使用箭头函数语法:

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]

14

使用ES2015函数式编程范式

计算两个数组之间的差异Set操作之一。该术语已经表明应该使用本地Set类型,以提高查找速度。无论如何,在计算两个集合之间的差异时,有三种排列方式:

[+left difference] [-intersection] [-right difference]
[-left difference] [-intersection] [+right difference]
[+left difference] [-intersection] [+right 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) );

正确的差异:

差分器很简单。它只是将参数翻转的差分器L。为方便起见,您可以编写一个函数:const differencer = flip(differencel)。 就这样!

对称的差异:

现在我们已经有了左和右的差异,实现对称的差异也变得很简单:

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

我觉得这个例子是获得函数式编程印象的好起点:

使用可以以许多不同方式组装在一起的构建块进行编程。


12

使用indexOf()的解决方案对于小数组来说是可以的,但随着数组长度的增加,算法的性能接近于O(n^2)。这里有一个解决方案,它将使用对象作为关联数组来存储数组条目作为键;它还会自动消除重复的条目,但仅适用于字符串值(或可以安全地存储为字符串的值):

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

每当您在对象上执行“for in”时,都要使用Object.hasOwnProperty()。否则,您会冒着循环遍历添加到默认对象原型(或仅父对象)的每个字段的风险。此外,您只需要两个循环,一个用于哈希表创建,另一个用于在该哈希表上查找。 - jholloman
1
@jholloman 我尊重地不同意(http://phrogz.net/death-to-hasownproperty)。现在我们可以控制任何属性的可枚举性,因此您应该包括在枚举期间获取的任何属性。 - Phrogz
1
@Phrogz 如果你只关心现代浏览器,那么这是一个好的观点。不幸的是,我在工作中必须支持IE7及以下版本,所以我的默认思路是石器时代,我们也不倾向于使用shims。 - jholloman

10

Joshaven Potter的上面的回答非常好。但它返回的是B数组中不在C数组中的元素,而不是相反的情况。例如,如果var a=[1,2,3,4,5,6].diff( [3,4,5,7]);,那么它会输出:[1,2,6],但不会输出[1,2,6,7],这才是两者之间的实际差异。您仍然可以使用Potter上面的代码,但只需反向再进行一次比较:

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

这应该输出:[ 1, 2, 6, 7 ]


8
如果您有两个对象列表
const people = [{name: 'cesar', age: 23}]
const morePeople = [{name: 'cesar', age: 23}, {name: 'kevin', age: 26}, {name: 'pedro', age: 25}]

let result2 = morePeople.filter(person => people.every(person2 => !person2.name.includes(person.name)))

这是一个很棒的答案。我点赞了它。大多数情况下,您将使用包含对象的数组进行工作......这对我今天有所帮助。谢谢Vikas。 - KingJoeffrey

8

使用JavaScript的filter函数非常简单:

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


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

你不应该以这种方式扩展本地对象。如果标准在将来的版本中引入了difference作为函数,并且该函数具有与您的函数签名不同的不同函数签名,则会破坏您的代码或使用此函数的外部库。 - t.niese

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接