javascript - Apakah algoritma yang baik untuk mencari penyatuan dua tatasusunan tolak persimpangan?

Question

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

Cari tatasusunan gabungan dua tatasusunan selepas mengalih keluar elemen pendua (merujuk kepada pemadaman elemen pendua pada kedua-dua belah, contohnya, jika 3 diulang, tidak boleh ada 3 dalam hasilnya, yang berbeza daripada penduaan tatasusunan), iaitu, kesatuan tolak persilangan bahagian tatasusunan, saya tidak tahu sama ada bahagian ini mempunyai sebarang nama matematik. Mencari algoritma dengan kerumitan masa yang lebih rendah?

Answer 1

Gunakan set sebagai indeks dan kemudian lintasi O(n) yang lebih pendek

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

Untuk mencari bahagian yang tidak bertindih bagi dua set, anda boleh mencari gabungan dua set itu dahulu, kemudian alih keluar elemen sepunya.
A∪B - A∩B = { x |. (x∈A & x∉B) || (x∉A & x∈B) }

Pelaksanaan menggunakan idea atur cara ialah:
Gabungkan dua tatasusunan, dan kemudian gunakan kaedah penapis untuk menapis elemen persilangan dalam tatasusunan a dan b. Tapis unsur-unsur dalam a.concat(b) di mana a bukan dalam b dan di mana b bukan dalam a. Ia terutamanya melibatkan pertimbangan sama ada tatasusunan mengandungi elemen Terdapat tiga kaedah pelaksanaan: Array.prototype.indexOf, Set's has method dan Array.prototype.includes.

Kaedah pelaksanaan menggunakan kaedah indexOf ES5 tanpa mengambil kira NaN:

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

Gunakan kaedah pengumpulan Set baharu dalam ES6 dan gabungkannya dengan kaedah penapis untuk menapis tatasusunan yang digabungkan.

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

Gunakan kaedah tatasusunan.prototype.includes baharu dalam ES7 untuk mengembalikan sama ada tatasusunan mengandungi elemen tertentu dan gabungkannya dengan kaedah penapis untuk menapis tatasusunan yang digabungkan.

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

Answer 3

Hasil ini dipanggil perbezaan simetri, yang ditakrifkan pada set atau multiset

Kerumitan... sederhana 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);

----------Saya salah baca soalan, jawapan salah, di atas hanya pendua yang dibuang, lihat di bawah-------------

----------Anda boleh menyelesaikannya dengan hanya melintasi asas untuk gelung-----------------

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

Kaedah pertama, untuk

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

Jenis kedua, concat dan penapis, prinsipnya adalah untuk menggabungkan dan kemudian mengeluarkan pendua

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

Answer 6

Menggunakan sifat objek untuk melaksanakan

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