Der effizienteste Weg, ein gemeinsames Objekt zwischen einer beliebigen Anzahl von Arrays zu finden

Question

Ich muss in der Lage sein, ein gemeinsames Element zwischen einer beliebigen Anzahl von Arrays zu finden. Zum Beispiel lassen Sie uns sagen, dass es ein Objekt wie folgt:

var obj = { 
    a: [ 15, 23, 36, 49, 104, 211 ], 
    b: [ 9, 12, 23 ], 
    c: [ 11, 17, 18, 23, 38 ], 
    d: [ 13, 21, 23, 27, 40, 85] 
}; 

Ich brauche würde das gemeinsame Element zwischen jedem dieser Arrays zu bestimmen. (In diesem Fall 23).

Meine Lösung besteht darin, das kürzeste Array zu finden und jedes Element darin zu durchlaufen und den Index der anderen Arrays zu überprüfen.

var shortest = {}; 
var keys = []; 
for (var key in obj) { 

    if (obj.hasOwnProperty(key) && Array.isArray(obj[ key ])) { 
    keys.push(key); 

    if (!shortest.hasOwnProperty('length') || obj[ key ].length < shortest.length) { 
     shortest.name = key; 
     shortest.length = obj[ key ].length; 
    } 
    } 
} 



var res = obj[ shortest.name ].filter(function (v) { 

    for (var i = 0; i < keys.length; i++) { 

    if (obj[ keys[ i ] ].indexOf(v) === -1) { 
     return false; 
    } 

    return true; 
    } 
}; 

Dies scheint jedoch enorm ineffizient, und ich versuche, um zu bestimmen, ob es eine bessere Art und Weise ist, vorzugsweise ohne mehrmals durch die Dinge zu Schleife.

Answer 1

Ich glaube nicht, dass es möglich ist, dies in weniger als O(N) zu tun, wobei N die Anzahl der Elemente in allen Arrays ist. Ihre aktuelle Lösung ist weniger effizient, da indexOfO(N) für jedes Array ist und Sie alle für jedes Element im kürzesten Array durchlaufen können.

Ich denke, eine kartenbasierte Option O(N) wäre:

var counts = {}; 
var keys = Object.keys(obj); 
var arr, el; 
for (var k = 0; k < keys.length; k++) { 
    arr = obj[keys[k]]; 
    for (var i = 0; i < arr.length; i++) { 
     el = arr[i]; 
     if (counts[el] === undefined) { 
      // new value, start counting 
      counts[el] = 1; 
     } else { 
      // increment count for this value 
      counts[el]++; 
      // if we have as many values as keys, we're done 
      if (counts[el] === keys.length) { 
       return el; 
      } 
     } 
    } 
} 

Einige Einsprüche hier:

• Dies setzt voraus, dass die Elemente verwendet werden können, als Objektschlüssel (dh sie eindeutig sein konvertiert in Strings), und Sie haben keine unangenehmen Randfälle wie 1 und "1" in verschiedenen Arrays.

• Dies setzt voraus, dass die Array-Werte für jedes Array eindeutig sind.

• Dies setzt voraus, dass es nur ein Element in der Kreuzung gibt.

https://jsfiddle.net/xzfa75og/

Answer 2

Eine weitere O(n) Vereinigungs Lösung, funktionell codiert. Die Einschränkung "Elemente als Objektschlüssel" gilt weiterhin, obwohl dadurch die Menge (Array) aller gemeinsam genutzten Elemente in der Schnittmenge zurückgegeben wird.

function common(o) { 
    // Map each of the object key arrays to a set. 
    return Object.keys(o).map(function(k) { 
    return o[k].reduce(function(a, e) { 
     a[e] = 1; 
     return a; 
    }, {}); 
    }).reduce(function(a, e) { 
    // Perform a set union. 
    Object.keys(e).forEach(function(k) { 
     if (!a[k]) { 
     delete e[k]; 
     } 
    }); 
    return e; 
    }) 
} 

var obj = { 
    a: [ 15, 23, 36, 49, 104, 211 ], 
    b: [ 9, 12, 23 ], 
    c: [ 11, 17, 18, 23, 38 ], 
    d: [ 13, 21, 23, 27, 40, 85] 
}; 

common(obj); 

Answer 3

Ich würde diesen Job durch eine Erfindung von Array.prototype.intersect() tun. Es wird nicht fehlschlagen, wenn doppelte Elemente im Array vorhanden sind. Wenn Sie dasselbe Element in jedem Array dupliziert haben, erhalten Sie das Duplikat in der Kreuzung, wie es sein sollte. Mal sehen, wie es

Array.prototype.intersect = function(...a) { 
 
     return [this,...a].reduce((p,c) => p.filter(e => c.includes(e))); 
 
    }; 
 
var obj = { 
 
      a: [ 15, 23, 36, 49, 104, 211 ], 
 
      b: [ 9, 12, 23 ], 
 
      c: [ 11, 17, 18, 23, 38 ], 
 
      d: [ 13, 21, 23, 27, 40, 85] 
 
      }, 
 
    arrs = Object.keys(obj).map(e => obj[e]); 
 

 
console.log(JSON.stringify(arrs.pop().intersect(...arrs))); // take the last one out to invoke the method over the rest

Answer 4

einfach eine andere Lösung in ES5 mit einem temporären Objekt in O (n) arbeiten.

var obj = { a: [15, 23, 36, 49, 104, 211], b: [9, 12, 23, 15], c: [11, 17, 18, 23, 38], d: [13, 21, 23, 27, 40, 85] }, 
 
    result = Object.keys(obj).reduce(function (o) { 
 
     return function (r, k, i) { 
 
      var t = o; 
 
      o = Object.create(null); 
 
      return obj[k].filter(function (a) { 
 
       return (!i || t[a]) && (o[a] = true); 
 
      }); 
 
     }; 
 
    }(Object.create(null)), []); 
 

 
console.log(result);