javascript - Quel est un bon algorithme pour trouver l'union de deux tableaux moins l'intersection?

Question

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

Trouvez le tableau fusionné de deux tableaux après avoir supprimé les éléments en double (en référence à la suppression des éléments en double des deux côtés, par exemple, si 3 est répété, il ne peut pas y avoir 3 dans le résultat, ce qui est différent de la déduplication de tableau), c'est-à-dire l'union moins l'intersection de la partie tableaux, je ne sais pas si cette partie a un nom mathématique. Vous recherchez un algorithme avec une complexité temporelle moindre ?

Answer 1

Utilisez set comme index, puis parcourez le O(n) le plus court

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]

Answer 2

Pour trouver les parties qui ne se chevauchent pas de deux ensembles, vous pouvez d'abord trouver l'union des deux ensembles, puis supprimer les éléments communs.
A∪B - A∩B = { x | (x∈A & x∉B) || (x∉A & x∈B) }

L'implémentation utilisant une idée de programme est la suivante :
Fusionnez les deux tableaux, puis utilisez la méthode de filtrage pour filtrer les éléments d'intersection dans les tableaux a et b. Filtrez les éléments dans a.concat(b) où a n'est pas dans b et où b n'est pas dans a. Cela implique principalement de déterminer si un tableau contient un élément. Il existe trois méthodes d'implémentation : Array.prototype.indexOf, la méthode has de Set et Array.prototype.includes.

Méthode d'implémentation utilisant la méthode indexOf d'ES5 sans considérer NaN :

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

Utilisez la nouvelle méthode de collection Set dans ES6 et combinez-la avec la méthode de filtrage pour filtrer le tableau fusionné.

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

Utilisez la nouvelle méthode de tableau Array.prototype.includes dans ES7 pour indiquer si un tableau contient des éléments spécifiés et combinez-la avec la méthode de filtrage pour filtrer le tableau fusionné.

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

Answer 3

Ce résultat est appelé différence symétrique, qui est définie sur un ensemble ou un multiensemble

Complexité... moyenne O(n)

Answer 4

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

----------J'ai lu la mauvaise question, la réponse est fausse, ce qui précède ne concerne que les doublons supprimés, voir ci-dessous-------------

---------------Vous pouvez le faire en parcourant simplement la boucle for de base--------------

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

Answer 5

La première méthode, pour

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

Le deuxième type, concaténer et filtrer, le principe est de fusionner puis de supprimer les doublons

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

Answer 6

Utiliser les propriétés des objets à implémenter

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

Capture d'écran