关于数组对象的算法问题，如何找到最优写法？

Question

let arr1 = [{
        is_gift:1,
        wg_id:111
        },{
        is_gift:1,
        wg_id:222
        },{
        is_gift:1,
        wg_id:333
}]
                    
let arr2 = [{
        is_gift:1,
        wg_id:111
        },{
        is_gift:3,
        wg_id:222
        },{
        is_gift:5,
        wg_id:444
        },{
        is_gift:4,
        wg_id:333
        },{
        is_gift:2,
        wg_id:555
}]

我有上面两个数组对象，我想通过这个两个数组中的wg_id这个字段相同，找出arr2中比arr1中多出的数据，其实我找到了一个方法， 但是我看着感觉比较复杂，所以想请大家帮忙看看有没有简单些的写法？

Answer 1

arr2.filter(item => !arr1.find(citem => citem.wg_id === item.wg_id))

Answer 2

找出处交叉值之外，第二个比第一个多出的数据吗？

Answer 3

let arr3 = arr2.filter(item => arr1.every(list => list.wg_id != item.wg_id))
let arr3 = arr2.filter(item => !arr1.some(list => list.wg_id == item.wg_id))

Answer 4

考虑下时间复杂度吧。。循环套循环不可取

const createMapbyId = (idKey, arr) => {
    return arr.reduce((obj, item) => {
        const key = item[idKey]
        obj[key] = item
        return obj
    },{})
}

const diff = (objA, objB) =>{
    return Object.keys(objA).reduce((arr, key) => {
        if(!(key in objB)) {
            arr.push(objA[key])
        }
        return arr
    }, [])
}
// 赋值。。。
const arr1 = []
const arr2 = []
const [arr1Map, arr2Map] = [arr1, arr2].map((arr) => createMapbyId('wg_id', arr))

diff(arr2Map, arr1Map)

Answer 5

我来给你分析一下

要想在 arr2 中找出来 arr1 中不存在的（多出来的），那么这里可以得到两个信息：

1. 要遍历 arr2，才会知道哪些是符合条件，哪些是不符合条件的，
2. 上述“条件”是批在 arr1 中不存在的，这就意味着需要在 arr1 中去查询指定数据，看是否存在。

数组是个线性表。对于上述第 2 点，查找最简单粗暴的方式就是遍历；另外在学数据结构的时候应该也学会映射表，可以根据 key 快速找到需要的东西，也就是常说的 map/dictionary。

在 1、2 都采用遍历方式的情况下，这是一个二重循环

const result = [];
for (var it2 of arr2) {
    let found = false;
    for (var it1 of arr1) {
        if (it2.wg_id === it1.wg_id) {
            // 既然存在，忽略它
            found = true;
            break;
        }
    }

    // 上面 for (it1) 循环完成都没找到，那就是没有
    if (!found) {
        result.push(it2);
    }
}
console.log(result);

接下来，如果你对 JS 的库函数比较熟悉的话（不熟悉就是看看 MDN 中 Array 的文档
），应该会知道它提供了 find() 用于查找，所以用于查找的内循环可以简化掉：

const result = [];
for (var it2 of arr2) {
    if (!arr1.find(it1 => it1.wg_id === it2.wg_id)) {
        result.push(it2);
    }
}
console.log(result);

现在只剩下的外层循环，这实际是一个“过滤”的操作，就是把符合条件或不符合条件（也就是符合相反条件）的元素找出来。在 Array 中对应的 API 是 filter()，所以可以再简化

const result = arr2.filter(it2 => !arr1.find(it1 => it1.wg_id === it2.wg_id));
console.log(result);

如果 it1 足够大的时候，遍历会比较耗时，这种情况下，可以用上面提到的映射表来解决，JS 对象本身就是一个映射表，也可以用 Map 类。生成 JS 对象可以使用 Object.fromEntries()，生成 Map 对象可以用 new Map(entries)（链接就不给了，去 MDN 查查）。他们所需要的 entries，就是键-值对集合（数组）而键值对在 JS 中也是使用数组来表示的（文档中有）：一个包含两个元素的数组，0 号位是键，1 号位是值。

要把 arr1 变成映射表，需要先把它处理成键值对。原数组和目标数组（键值对数组）是一对一的关系，可以使用 map() 来实现

const entries = arr1.map(it1 => [it1.wg_id, it1]);
const map = Object.fromEntries(entries);

其中 entries 只使用一次，可以内联到 Object.fromEnties() 中，两句变一句，少写个变量。

生成映射表之年，查找就变成了映射表查找，对于 JS 对象来说，可以用 in 关键字（还有一些其他方法，可以自己去研究）

const result = arr2.filter(it2 => !(it2.wg_id in map));

观察发现，其实只需要判断键是否存在，不需要用 Map，只需要用 Set 保存所有键即可。代码如下，就不解释了

使用了解构语法，如果不清楚可以去了解一下。换成普通的箭头函数也是可以的。

const set = new Set(arr1.map(({ wg_id }) => wg_id));
const result = arr2.filter(it2 => !set.has(it2.wg_id));