javascript - What is a good algorithm for finding the union of two arrays minus the intersection?
过去多啦不再A梦
过去多啦不再A梦 2017-06-26 10:51:43
0
6
1523
var arr1 = [1,2,3,4,5,6,7]
var arr2 = [3,5,7,9,12,14]

Find the merged array of two arrays after removing duplicate elements (referring to deleting the duplicate elements on both sides, for example, if 3 is repeated, there cannot be 3 in the result, which is different from array deduplication), that is, the union of the arrays The part of subtracting the intersection, I don’t know if this part has any mathematical name. Looking for an algorithm with lower time complexity?

过去多啦不再A梦
过去多啦不再A梦

reply all(6)
大家讲道理

Use set as index and then traverse the shorter 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]
为情所困

To find the non-overlapping parts of two sets, you can first find the union of the two sets, and then remove the common elements.
A∪B - A∩B = { x | (x∈A & x∉B) || (x∉A & x∈B) }

The implementation using the program idea is:
Merge the two arrays, and then use the filter method to filter out the intersection elements in arrays a and b. Filter out the elements in a.concat(b) where a is not in b and where b is not in a. It mainly involves the judgment of whether an array contains an element. There are three implementation methods: Array.prototype.indexOf, Set's has method, and Array.prototype.includes.

Implementation method using ES5’s indexOf method without considering NaN:

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

Use the new Set collection method in ES6 and combine it with the filter method to filter the merged array.

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

Use the new Array.prototype.includes array method in ES7 to return whether an array contains specified elements, and combine it with the filter method to filter the merged array.

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

This result is called symmetric difference, which is defined on set or multiset

Complexity...generally 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);

----------I read the wrong question, the answer is wrong, the above is just the duplicates removed, see below-------------

----------You can get it done by just traversing the basic for loop---------------

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

The first method, for

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

The second type, concat and filter, the principle is to merge and then remove duplicates

var arr=arr1.concat(arr2);
arr=arr.filter(function(item,index,self){
    return self.indexOf(item) == index;
});
女神的闺蜜爱上我

Using the properties of objects to implement

var arr2key = (arr, o = {}) => {
    return arr.reduce((acc, cur) => {
        acc[cur] = '√'; 
        return acc; 
    }, o); 
}

var mergeAsObj = A => B => {
    return arr2key(B, arr2key(A)); 
}

var obj2arr = Object.keys; 

// 组装 
var arrMerge = A => B => {
    return obj2arr(
        mergeAsObj(A)(B)
    )
}

ScreenShot

Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template