Rumah  >  Soal Jawab  >  teks badan

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

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?

过去多啦不再A梦过去多啦不再A梦2696 hari yang lalu1496

membalas semua(6)saya akan balas

  • 大家讲道理

    大家讲道理2017-06-26 10:53:43

    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]

    balas
    0
  • 为情所困

    为情所困2017-06-26 10:53:43

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

    balas
    0
  • 伊谢尔伦

    伊谢尔伦2017-06-26 10:53:43

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

    Kerumitan... sederhana O(n)

    balas
    0
  • 仅有的幸福

    仅有的幸福2017-06-26 10:53:43

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

    balas
    0
  • 黄舟

    黄舟2017-06-26 10:53:43

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

    balas
    0
  • 女神的闺蜜爱上我

    女神的闺蜜爱上我2017-06-26 10:53:43

    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

    balas
    0
  • Batalbalas