请教两个数组对比的问题

https://github.com/YuJianrong/fast-array-diff

this

好奇怪的需求啊,执行完 arr2 不在 arr1 的删除,就是[a,b,c,d],是取交集,那第二步 arr1 元素加入到 arr2,arr2 不就和 arr1 相同了?

如果是分开的话:
arr2.filter((x)=>arr1.includes(x))
arr2.concat(arr1.filter(x=>!arr2.includes(x)))

遍历做哈希，然后遍历比较，时间复杂度是 O(n)

那结果不就是 arr1 吗....还是说 arr1 和 arr2 里有重复元素，所以结果是 arr1 先去重然后加入 arr2 里的重复元素？

使用 HashSet 的快速查找功能，利用空间换时间，效率为 O(n)。
创建 arr1Set
创建 arr2Set
然后再分别遍历 arr2 和 arr1 进行处理。

@NessajCN
@paopjian

确实结果是 arr1 ，但是不能用 arr1 去替换 arr2 ，因为 arr2 中的元素是对象，同样是 a 元素，唯一标识相同、字段名相同，但是字段的值在 arr2 中有修改过。

let arr3 = Array.from(new Set(arr2.filter(x => (new Set(arr1)).has(x)).concat(arr1)))

@NessajCN
@paopjian

而且顺序也不一样。

老老实实写没错的

用带顺序的集合试试？顺序控制自建一个比较函数，或者加个序号，然后直接求差集、交集。

已经是 O(n)了, 真的还能有更好的吗?

这和我做的一个表格表头同步的需求很像

``` Javascript
// 返回用 arr2 中的对象更新 arr1 后的数组，数组按 arr2 中相对顺序排序
function merge(arr1, arr2) {
const map = new Map();
const ans = [];
arr1.forEach((obj) => map.set(obj.id, obj));
arr2.forEach((obj) => {
if (map.has(obj.id)) {
ans.push(obj);
map.delete(obj.id);
}
});
return ans.concat(Array.from(map.values()));
}
```

整两个 set 做交并补吧

需求目的就是把 arr1 的元素复制到 arr2 并且删除 arr1 没有的元素。
那么对两个数组分别 set ，找出差集，双指针扫一遍，复杂度 Onlogn

感觉优化的空间不是很大。

```js
const map1 = new Map()
const map2 = new Map()
arr1.forEach(e => {
map1.set(e.key, e)
});
arr2.forEach(e => {
if (map1.has(e.key)) {
map2.set(e.key, e)
}
});
arr1.forEach(e => {
if (!map2.has(e.key)) {
map2.set(e.key, e)
}
});
console.log(map2.values())
```

// 写了一段 兼容 IE6
// 只存在一次两层循环
// 循环的过程中重新建 2 个数组，数组里面放新的对象，对象里面把原始值存进去，加个计数值

var arr1=["a","b","c","d","e","f","a","b","a","b"] //字符串意思意思，代替相同的对象
var arr2=["a","b","c","c","c","c","z","z","z","a"]
var arr11=[],arr22=[];

for(var i=0;i<arr1.length;i++){
arr11.push({value:arr1[i], hit:0});
}
for(var i=0;i<arr2.length;i++){
var obj2={value:arr2[i], hit:0};
arr22.push(obj2);
for(var j=0;j<arr11.length;j++){ //给 arr11 计数
var obj1=arr11[j];
if(obj1.value==obj2.value){ //自行比较两个对象是否相等
obj1.hit++;
obj2.hit++;
}
}
}

//得到已存在的结果
arr2.length=0; //?
for(var i=0;i<arr22.length;i++){
if(arr22[i].hit){
arr2.push(arr22[i].value);
}
}
//添加缺失的
for(var i=0;i<arr11.length;i++){
if(!arr11[i].hit){
arr2.push(arr11[i].value);
}
}

console.log(arr2);

@FishBear 作为作者，我要说明一下 fast-array-diff 不是用在这个场景的。
fast-array-diff 是为了找出一个有序系列转换到另一个有序系列的步骤。
这个问题的场景是无序的。

已经 O(n)了，要是排序好的数组，应该还能优化

arr2.filter(i => !arr1.includes(i)).forEach(i => {
const index = arr1.indexOf(i);
if (index !== -1) {
arr1.splice(index, 1);
} else {
arr1.push(i);
}
});