获取两个数组之间的差异（包括重复项）

Question

我看到很多文章都在介绍如何在JavaScript中获取数组的差异和对称差异，但我没有找到关于如何找到包含重复项的差异的任何内容。

例如：

let original = [1];
let updated = [1, 1, 2];

difference(updated, original);
// Expect: [1, 2]

有一种优雅的方法可以做到这一点吗？我可以接受使用纯JavaScript或Lodash的解决方案。

谢谢！

更新

澄清一下，应该支持无限数量的重复。另一个例子：

let original = [1, 1];
let updated = [1, 1, 1, 1, 1, 2];

difference(updated, original);
// Expect: [1, 1, 1, 2]

更新2

我意识到原始需求可能存在一些混淆。无限制的复制应该是被支持的，但顺序不应影响输出。

例如：

let original = [1, 1, 2];
let updated = [1, 2, 1, 1, 1];

difference(updated, original);
// Expect: [1, 1]

- jdixon04

---

你对这个案例 let original = [1, 5]; let updated = [1, 1, 2]; 有什么期望？ - suraj.tripathi

[1,1,1,1]和[1,2]之类的问题...重复的1有多少个？规则需要更加明确。 - charlietfl

感谢您的输入。请参见上面的更新，应该可以回答您的问题。 - jdixon04

输出的顺序怎么样？有什么要求吗？difference([1, 2, 3, 3, 1], [3, 2, 1, 2]) 的输出结果会是什么？ - trincot

对于任何数组 a 和 b，必须确保 difference(a, b) 给出的结果和 difference(b, a) 相同。 - trincot

Answer 1

我建议采用以下解决方案，避免时间复杂度为O(n²)：

function difference(a, b) {
    return [...b.reduce( (acc, v) => acc.set(v, (acc.get(v) || 0) - 1),
            a.reduce( (acc, v) => acc.set(v, (acc.get(v) || 0) + 1), new Map() ) 
    )].reduce( (acc, [v, count]) => acc.concat(Array(Math.abs(count)).fill(v)), [] );
}

let original = [1, 1];
let updated = [1, 1, 1, 1, 1, 2];
let res = difference(updated, original);

console.log(res);

说明

该解决方案创建了一个Map，其中的每个键都对应于第一个数组（a）的每个不同值，并且作为相应值的是出现次数。然后以同样的方式将b添加到该Map中，但是出现次数计为负数。如果该计数最终等于零，则该键在最终结果中不应出现。实际上，最终结果中每个键的出现次数是其在Map中计数的绝对值。

详细信息

代码起始如下：

new Map()

这是内部 reduce 累加器的初始值。该 reduce 遍历 a 并在 Map 中更新相应键的计数。因此，这个 reduce 的最终结果是一个 Map。

然后这个 Map 成为外部 reduce 的初始累加器值。该 reduce 遍历 b 并减少 Map 中的计数。

这个更新过的 Map 是用扩展运算符放入一个数组中的。这个数组由2元素子数组组成，它们是键/值对。请注意，在这种情况下，值是可以是正数、零或负数的计数。

然后使用最终的 reduce 遍历这个数组。每个计数都用于创建与相应值数量（按绝对值）相同的元素数组。所有这些都连接到一个数组中，作为函数的返回值。

跟进问题

在评论中，您解释了实际上需要不同的内容，其中两个数组的角色不同。第一个数组应该被返回，但是从第二个数组中删除元素。

您可以使用以下代码实现：

function difference2(a, b) {
    return a.filter(function(v) {
        return !this.get(v) || !this.set(v, this.get(v) - 1);
    }, b.reduce( (acc, v) => acc.set(v, (acc.get(v) || 0) + 1), new Map() ));
}

let original = [1, 1, 2];
let updated = [1, 1];
let res = difference2(original, updated);

console.log(res);

- trincot

---

谢谢你的比较。我已经很久没有看到与时间复杂度相关的内容了，所以非常感谢这个详细的概述！ - jdixon04

为了上下文的理解，这些数组存储着“id”值。其中一个包含新值，另一个包含原始值。当我进行比较时，我需要说明是否正在添加差异数组中的记录或者是否正在删除这两个数组的差异记录。 - jdixon04

我在我的答案中添加了一个额外的部分和脚本。不过下次，你应该将这样的跟进问题作为一个新问题来问。这两个问题并不相同。但是这一次没有问题 :) - trincot

@trincot 我刚刚更新了我的答案并进行了速度测试，你的表现要好得多。 :) 然而，由于我的函数速度较慢，我成功崩溃了三次选项卡并失去了所有进展。 :D - StardustGogeta

啊，干得好，@StardustGogeta——不是崩溃，而是测试当然没问题 :D - trincot

Answer 2

function count(n,arr) {
  return arr.filter(a=>a==n).length
}

function diffBetween(arr,arr2) {
  diff = [];
  new Set(arr.concat(arr2)).forEach(
  a => {
    for(x=0;x<Math.abs(count(a,arr)-count(a,arr2));x++)
      diff.push(a)
    }
  );
  return diff;
}

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

这对你有什么帮助？

这对你有什么帮助？

编辑：

function difference(a, b) { // trincot's code
    return [...b.reduce( (acc, v) => acc.set(v, (acc.get(v) || 0) - 1),
            a.reduce( (acc, v) => acc.set(v, (acc.get(v) || 0) + 1), new Map() ) 
    )].reduce( (acc, [v, count]) => acc.concat(Array(Math.abs(count)).fill(v)), [] );
}

function count(n,arr) { // My code
  return arr.filter(a=>a==n).length
}

function diffBetween(arr,arr2) { // My code
  diff = [];
  new Set(arr.concat(arr2)).forEach(
  a => {
    for(x=0;x<Math.abs(count(a,arr)-count(a,arr2));x++)
      diff.push(a)
    }
  );
  return diff;
}

in1 = [1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2,1,1,1,1,1,1,2,2,2,2,2,2,2];
in2 = [1,2,3,4,5,6,1,2,3,4,5,6,7,1,1,1,1,1,1,2,2,2,2,2,2,2];

start = (new Date).getTime();
a = difference(in1,in2);
end = (new Date).getTime();
console.log("trincot done",end-start,"msec");
start = (new Date).getTime();
a = diffBetween(in1,in2);
end = (new Date).getTime();
console.log("stardust done",end-start,"msec");

的解决方案在我的测试中始终更快，因此对于足够大的数据集，他的方案显然更优。

- StardustGogeta

Answer 3

所以，我会:

• 迭代更新后的数组，对于每个元素，检查它是否存在于原始数组中，如果存在，则从原始数组中删除它（注意：在下面的函数中，我复制了原始对象，因此不会影响它），否则将其推送到差异数组中。最后，我返回差异数组。

---

这段代码是为了在各种浏览器上正常运行，因此我没有使用 ECMAScript 的 Array().indexOf 和其他较新的方法。

function difference(updated, original) {
  var i, l;
  /* copy original array */
  var degradation = [];
  for (var i = 0, ol = original.length; i < ol; ++i)
    degradation[i] = original[i]

  var diff = [];
  for (i = 0, l = Math.max(updated.length, ol); i < l; ++i) {
    var upd = updated[i];
    var index;
    var b, found;
    /* find updated item in degradation */
    for (b = 0, found = false; b < ol; ++b) {
      if (degradation[b] === upd) {
        /* remove item from degradation */
        delete degradation[b];
        found = true;
        break;
      }
    }
    if (!found)
      diff.push(upd);
  }
  return diff;
}

- user5066707

Answer 4

你可以按照以下步骤进行；

var original = [1, 1, 1, 1, 2],
     updated = [1, 2, 1, 1, 3],
      result = (...a) => { var [shorter,longer] = [a[0],a[1]].sort((a,b) => a.length - b.length),
                                              s = shorter.slice();
                           return shorter.reduce((p,c) => { var fil = p.indexOf(c),
                                                                fis = s.indexOf(c);
                                                            fil !== -1 && (p.splice(fil,1),s.splice(fis,1));
                                                            return p;
                                                          },longer).concat(s);
                         };
console.log(result(updated,original));

- Redu

---

尝试在reduce中反转数组...会得到不同的结果。 - charlietfl

@redu 很遗憾，这个解决方案在以下情况下会失败：let original = [1, 1, 1, 1, 2]; let updated = [1, 2, 1, 1, 3]; // 预期结果: [1,3] 实际结果: [3] - jdixon04

@jdixon04 感谢你的警告... 我想这样应该可以了。 - Redu

Answer 5

您可以按照以下步骤（O(n)）进行操作。

假设a和b是两个数组

步骤1. 创建一个名为hash_map的映射，将数组a的值作为键，该键的出现次数作为值。

步骤2. 使用hash_map将数组b中不在a中的所有元素推入result。

步骤3. 使用hash_map将数组a中不在b中的所有元素推入result。

以下是完整代码

function diff(a, b) {
    //Step 1 starts here
 var hash_map = a.reduce(function(map, key) {
  map[key] = map[key] ? (map[key]+1) : 1;
  return map;
 }, {});
    //Step 1 ends here
    //Step 2 starts here
 var result = b.filter(function(val) {
  if(hash_map[val]) {
   hash_map[val] = hash_map[val]-1;
   return false;
  }
  return true;
 });
    //Step 2 ends hers
    //Step 3 starts here
 Object.keys(hash_map).forEach(function(key) {
  while (hash_map[key]) {
   result.push(key);
   hash_map[key] = hash_map[key]-1;
  }
 });
    //Step 3 ends here
 return result;
}

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

- suraj.tripathi

Answer 6

    Array.prototype.Diff = function( secondArray ) {
    var mergedArray = this.concat( secondArray );
    var mergedString = mergedArray.toString();
    var finalArray = new Array();

    for( var i = 0; i < mergedArray.length; i++ ) {
        if(mergedString.match(mergedArray[i])) {
            finalArray.push(mergedArray[i]);
            mergedString = mergedString.replace(new RegExp(mergedArray[i], "g"), "");
        }
    }
    return finalArray;
}

var let = [ 1 ];
var updated = [ 1, 1, 2 ];

console.log(let.Diff(updated));

我喜欢原型方式。你可以将原型函数保存在JS文件中，并在任何想要的页面中导入，然后可以将其用作对象（在这种情况下为数组）的嵌入式函数。

- Fabricio

---

如果您在其中一个数组中输入10而不是1，那个字符串方法就会出错。 - charlietfl

你说得对，我没有注意到这个字符串和正则表达式，谢谢。 - Fabricio