Heim  >  Fragen und Antworten  >  Hauptteil

javascript - Was ist ein guter Algorithmus zum Ermitteln der Vereinigung zweier Arrays minus der Schnittmenge?

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

Suchen Sie das zusammengeführte Array aus zwei Arrays, nachdem Sie doppelte Elemente entfernt haben (bezieht sich auf das Löschen der doppelten Elemente auf beiden Seiten. Wenn beispielsweise 3 wiederholt wird, darf das Ergebnis keine 3 enthalten, was sich von der Array-Deduplizierung unterscheidet), d. h. die Vereinigung minus der Schnittmenge des Array-Teils, ich weiß nicht, ob dieser Teil einen mathematischen Namen hat. Suchen Sie einen Algorithmus mit geringerer zeitlicher Komplexität?

过去多啦不再A梦过去多啦不再A梦2696 Tage vor1499

Antworte allen(6)Ich werde antworten

  • 大家讲道理

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

    用 set 做索引再遍历较短的 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]

    Antwort
    0
  • 为情所困

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

    求两个集合不重合的部分,可以先求两个集合的并集,然后去掉公共的元素。
    A∪B - A∩B = { x | (x∈A & x∉B) || (x∉A & x∈B) }

    用程序的思路来实现是:
    对两个数组合并,然后使用filter方法过滤掉数组a和b中的交集元素。将a.concat(b)中在a不在b中和在b不在a中的元素过滤出来。主要会涉及到数组中是否含有某个元素的判断,有Array.prototype.indexOf,Set的has方法,Array.prototype.includes三种实现方式。

    利用ES5的indexOf方法在不考虑NaN情况下的实现方法:

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

    利用ES6新增的Set集合方法,结合filter方法对合并的数组进行过滤。

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

    利用ES7新增的Array.prototype.includes数组方法,用于返回一个数组是否包含指定元素,结合filter方法对合并的数组进行过滤。

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

    Antwort
    0
  • 伊谢尔伦

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

    這個結果叫symmetric difference, 在set或multiset上都有定義

    複雜度..一般就O(n)

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

    ----------看错问题了,答案有误,上面的只是去重了,看下面-------------

    ----------基础的for循环遍历一下就能搞定---------------

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

    Antwort
    0
  • 黄舟

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

    第一种方法,for

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

    第二种,concat和filter,原理就是合并再去重

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

    Antwort
    0
  • 女神的闺蜜爱上我

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

    利用对象的性质实现

    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

    Antwort
    0
  • StornierenAntwort