得到两个数组之间的差异(包括重复项) [英] get difference between two arrays (including duplicates)

问题描述

我看到很多关于如何在javascript中获得数组的差异和对​​称差异的文章，但是我还没有找到有关如何找到差异的任何信息，包括重复项.

I see a lot of posts about how to get the difference and symmetric difference of an array in javascript, but I haven't found anything on how to find the difference, including duplicates.

例如:

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

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

是否有一种优雅的方法来做到这一点?我愿意使用普通的javascript或lodash解决方案.

Is there an elegant way to do this? I'm open to solutions using plain javascript or lodash.

谢谢！

更新

为澄清起见，应支持无限数量的重复项.另一个例子:

To clarify, an infinite number of duplicates should be supported. Another example:

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

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

更新2

我意识到原始要求可能会有些混乱.确实应该支持无限重复，但是顺序不应影响输出.

I realized that there may be some confusion on the original requirements. It is true that infinite duplicates should be supported, but the order should not affect the output.

示例:

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

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

推荐答案

我建议采用这种解决方案，它避免了 O(n²)的时间复杂度:

I would suggest this solution, which avoids a time complexity of 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);

此解决方案使用第一个数组( a )的每个不同值创建一个带有键的Map，并作为每个值的出现次数作为值.然后以相同的方式将 b 添加到该Map中，不同之处在于出现次数为负.如果该计数最终为零，那么此键当然不应最终结果.实际上，最终结果中出现的次数是Map中每个键的计数的绝对值.

This solution creates a Map with a key for every distinct value of the first array (a), and as value the count of occurrences of each. Then b is added to that Map in the same way, except that the count of occurrences counts negative. If that count ends up being zero, then of course this key should not end up in the final result. In fact, the number of occurrences in the final result is the absolute value of the count in the Map for each of its keys.

代码以:

new Map()

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

It is the initial value of the accumulator of the inner reduce. That reduce iterates over a and updates the count of the corresponding key in the Map. The final result of this reduce is thus a Map.

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

This Map then becomes the initial accumulator value for the outer reduce. That reduce iterates over b and decreases the count in the Map.

此更新的Map通过传播运算符传播到一个数组中.该数组由2个元素的子数组组成，它们是键/值对.请注意，在这种情况下，该值是一个可以为正，零或负的计数.

This updated Map is spread into an array with the spread operator. This array consists of 2-element sub-arrays, which are key/value pairs. Note that the value in this case is a count which could be positive, zero or negative.

然后使用最终的reduce迭代此数组.每个计数用于创建一个数组，其中包含对应值的多个元素(绝对值).所有这些都连接到一个数组，即该函数的返回值.

This array is then iterated with the final reduce. Each count is used to create an array of that many elements (in absolute value) of the corresponding value. All this is concatenated to one array, being the return value of the function.

在注释中，您解释了您实际上需要一些不同的东西，其中两个数组的角色不同.应该返回第一个数组，但要删除第二个数组中的元素.

In comments you explained you actually needed something different, where the role of both arrays is not the same. The first array should be returned, but with the elements from the second array removed from it.

您可以为此使用以下代码:

You could use this code for that:

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

这篇关于得到两个数组之间的差异(包括重复项)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！