【JS】求两个数组的并集减去交集的部分，有什么好的算法？

Z时代
2024-01-10
分类：技术分享

var arr1 = [1,2,3,4,5,6,7]var arr2 = [3,5,7,9,12,14]

求两个数组的去除重复元素后(指将两边的重复元素都删除，例如3重复，则在结果中不能有3，与数组去重不同)的合并的数组，即数组的并集减交集的部分，不知道这个部分有什么数学名称没有。求一个时间复杂度较低的算法？

回答

求两个集合不重合的部分，可以先求两个集合的并集，然后去掉公共的元素。
A∪B - A∩B = { x | (x∈A & x∉B) || (x∉A & x∈B) }

用程序的思路来实现是：
对两个数组合并，然后使用filter方法过滤掉数组a和b中的交集元素。将a.concat(b)中在a不在b中和在b不在a中的元素过滤出来。主要会涉及到数组中是否含有某个元素的判断，有Array.prototype.indexOf，Set的has方法，Array.prototype.includes三种实现方式。

利用ES5的indexOf方法在不考虑NaN情况下的实现方法：

function difference(a,b) {
    return a.concat(b).filter(function(v) {
        return a.indexOf(v) === -1 || b.indexOf(v) === -1
    })}

利用ES6新增的Set集合方法，结合filter方法对合并的数组进行过滤。

function difference(a, b) {
    let aSet = new Set(a)
    let bSet = new Set(b)
    return a.concat(b).filter(v => !aSet.has(v) || !bSet.has(v))}

利用ES7新增的Array.prototype.includes数组方法，用于返回一个数组是否包含指定元素，结合filter方法对合并的数组进行过滤。

function difference(a, b) {
    return a.concat(b).filter(v => !a.includes(v) || !b.includes(v))}

用 set 做索引再遍历较短的 O(n)

var s1 = new Set(arr1)
var s2 = new Set(arr2)
if (s1.size > s2.size) { [s1, s2] = [s2, s1] } // 让 s1 较短
s1.forEach(n => s2.has(n) && (s1.delete(n), s2.delete(n)))var result = [...s1, ...s2]

這個結果叫symmetric difference, 在set或multiset上都有定義

複雜度..一般就O(n)了

var arr1 = [1,2,3,4,5,6,7];
var arr2 = [3,5,7,9,12,14];
const s = new Set();
let arr = arr1.concat(arr2);
arr.forEach(x => s.add(x));console.log(s);

----------看错问题了，答案有误，上面的只是去重了，看下面-------------

----------基础的for循环遍历一下就能搞定---------------

var arr1 = [1,2,3,4,5,6,7];
var arr2 = [3,5,7,9,12,14];
var arr = [];
for(let i=0; i < arr1.length; i++){
    if (!arr2.includes(arr1[i])) {
        arr.push(arr1[i]);
    }
}
for(let i=0; i < arr2.length; i++){
    if (!arr1.includes(arr2[i])) {
        arr.push(arr2[i]);
    }
}
console.log(arr);

第一种方法，for

for(let i=0,len=arr2.length;i++){
    if(arr1.indexOf(arr2[i])===-1){
        arr1.push(arr2[i]);
    }
}

第二种，concat和filter，原理就是合并再去重

var arr=arr1.concat(arr2);
arr=arr.filter(function(item,index,self){
    return self.indexOf(item) == index;});

本人想起一种算法，利用哈希表，时间复杂度应该是O(n)，但是耗费一定的空间，不知是否有更好的解法，代码如下：

function getResult(arr1,arr2){
    var obj = {};
    arr1.forEach(function(item){
        obj[item] = true;
    })
    arr2.forEach(function(item){
        if(obj[item]){
            obj[item] = false;
        }
        else{
            obj[item] = true;
        }
    })
    var res = [];
    for(var p in obj){
        if(obj[p]){
            res.push(parseInt(p))  
        }
    }
    return res;
    // return Object.keys(obj).filter(function(item){
    //     return obj[item] == true;
    // })}

方法一，查询表

var arr1 = [1, 2, 3, 4, 5, 6, 7];
var arr2 = [3, 5, 7, 9, 12, 14];
// 生成表1
var set1 = arr1.reduce((all, n) => {
    return all.add(n);
}, new Set());
// 生成表2
var set2 = arr2.reduce((all, n) => {
    return all.add(n);
}, new Set());
// 找到列表1中不存在于列表2的
var result1 = arr1.filter(n => !set2.has(n));
// 找到列表2中不存在于列表1的
var result2 = arr2.filter(n => !set1.has(n));
// 组合起来var result = [...result1, ...result2];

方法二，统计计重

// 合并两个列表
const all = [...arr1, ...arr2]
    .reduce((all, n) => {
        // 对每个值计数
        all.set(n, (all.get(n) || 0) + 1);
        return all;
    }, new Map());
// 选取计数为 1 的
result = Array.from(all.keys())    .filter(n => all.get(n) === 1);

结果都是：[ 1, 2, 4, 6, 9, 12, 14 ]

补充一下

如果不用 ES6，可以使用第一种方法，去掉生成 set 的过程，把 set.has() 改成按数组遍历查找。