算法 - JavaScript数组系列问题：数组差集

Question

JavaScript求出两个数组的差集，下面是我实现的方法

function arrayDiffSet(a, b) {

    if ((!a || !a.length) && (b && b.length)) {
        return b
    } else if ((!b || !b.length) && (a && a.length)) {
        return a
    }

    var aMap = {},
        _aMap = {},
        _bMap = {};

    for (var i = 0, length = a.length; i < length; i++) {
        aMap[a[i]] = _aMap[a[i]] = true;
    }

    for (var i = 0, length = b.length; i < length; i++) {
        if (aMap[b[i]]) {
            delete _aMap[b[i]];
        } else {
            _bMap[b[i]] = true;
        }
    }

    return {
        a: Object.keys(_aMap),
        b: Object.keys(_bMap)
    }

}

function generateRandomArray(length, range) {
    var result = [];
    for (var i = 0; i < length; i++) {
        result[result.length] = Math.floor(Math.random() * range);
    }
    return result
}

var a = generateRandomArray(5, 10);
var b = generateRandomArray(10, 10);

console.log('a', a);
console.log('b', b);

console.time('start');
console.log(arrayDiffSet(a, b));
console.timeEnd('start');

----------但是这个方法还有下面两点：
1、扩展性差，如果我需要返回的差集不去重，那需要再重新写一个方法；
2、没有办法对对象数组求差集；

所以在这里想问问各位大神有没有更优的解决方案

Answer 1

我代码写的不好。

不过求差集好像filter一下就可以了。

var a = generateRandomArray(5, 10);
var b = generateRandomArray(10, 10);

// 不去重
var result = {
    a: a.filter(el => !b.includes(el)),
    b: b.filter(el => !a.includes(el))
}

// 去重
var result2 = {
    a: [...new Set(a)].filter(el => !b.includes(el)),
    b: [...new Set(b)].filter(el => !a.includes(el))
}

// 合并一下
function diffSet(a, b, noDup) {
    if (noDup) {
        a = [...new Set(a)];
        b = [...new Set(b)];
    }
    return {
        a: a.filter(el => !b.includes(el)),
        b: b.filter(el => !a.includes(el))
    }
}

至于对象数组。。。太麻烦了，等你先把这个看明白了再说：lodash.isEqual

---

不使用ES6:

// 不去重
// 使用indexOf代替includes

a.filter(function(el){
    return b.indexOf(el) == -1;
});

// 去重
// 引入index先对a自身去重

a.filter(function(el, idx){
    return a.indexOf(el) == idx && b.indexOf(el) == -1;
});

Answer 2

新方法：

/**
 * 新方法
 * @param {Object} a
 * @param {Object} b
 * @param {Object} isDup 是否不去重（默认去重）
 */


function arrayDiffSet(a, b, isDup) {

    var al = a.length,
        bl = b.length;

    if ((!a || !al) && (b && bl)) {
        return b
    } else if ((!b || !bl) && (a && al)) {
        return a
    }

    var i = 0,
        aMap = {},
        _aMap = {},
        _bMap = {},
        _a = [],
        _b = [],
        temp;

    for (i = 0; i < al; i++) {
        temp = a[i];
        aMap[temp] = true;
        !_aMap[temp] ? _aMap[temp] = [] : '';
        _aMap[temp][_aMap[temp].length] = temp;
    }

    for (i = 0; i < bl; i++) {
        temp = b[i];
        if (aMap[temp]) {
            delete _aMap[temp];
        } else {
            _b[_b.length] = temp;
            _bMap[temp] = true;
        }
    }

    if (isDup) {
        for (var item in _aMap) {
            _a = _a.concat(_aMap[item]);
        }

        return {
            a: _a,
            b: _b
        }
    }

    return {
        a: Object.keys(_aMap),
        b: Object.keys(_bMap)
    }

}

function generateRandomArray(length, range) {
    var result = [];
    for (var i = 0; i < length; i++) {
        result[result.length] = Math.floor(Math.random() * range);
    }
    return result
}

var a = generateRandomArray(1000, 1000);
var b = generateRandomArray(1000, 1000);

console.log(a);
console.log(b);

console.time('start');
console.log(arrayDiffSet(a, b, true));
console.timeEnd('start');

另附：jQuery也是可以去重的
var a = [1, 2, 3, 4];
var b = [1, 2, 4, 5];
var c = $(a).not(b);
c = c.toArray(); // [3]