Einfachste Code für Array Schnittpunkt in Javascript

Question

Was ist die einfachste, Bibliothek-freien Code für die Umsetzung von Array-Kreuzungen in Javascript? Ich möchte schreiben

intersection([1,2,3], [2,3,4,5])

und erhalten

[2, 3]

Answer 1

Mein Beitrag in Bezug auf ES6. Im Allgemeinen findet er die Schnittmenge eines Arrays mit einer unbestimmten Anzahl von Arrays, die als Argumente angegeben werden.

Array.prototype.intersect = function(...a) {
  return [this,...a].reduce((p,c) => p.filter(e => c.includes(e)));
}
var arrs = [[0,2,4,6,8],[4,5,6,7],[4,6]],
     arr = [0,1,2,3,4,5,6,7,8,9];

document.write("<pre>" + JSON.stringify(arr.intersect(...arrs)) + "</pre>");

Answer 2

Wie wäre es, einfach assoziative Arrays zu verwenden?

function intersect(a, b) {
    var d1 = {};
    var d2 = {};
    var results = [];
    for (var i = 0; i < a.length; i++) {
        d1[a[i]] = true;
    }
    for (var j = 0; j < b.length; j++) {
        d2[b[j]] = true;
    }
    for (var k in d1) {
        if (d2[k]) 
            results.push(k);
    }
    return results;
}

を編集します。

// new version
function intersect(a, b) {
    var d = {};
    var results = [];
    for (var i = 0; i < b.length; i++) {
        d[b[i]] = true;
    }
    for (var j = 0; j < a.length; j++) {
        if (d[a[j]]) 
            results.push(a[j]);
    }
    return results;
}

Answer 3

Wenn Sie mehrere Arrays überschneiden wollen, können Sie dies tun:

const intersect = (a1, a2, ...rest) => {
  const a12 = a1.filter(value => a2.includes(value))
  if (rest.length === 0) { return a12; }
  return intersect(a12, ...rest);
};

console.log(intersect([1,2,3,4,5], [1,2], [1, 2, 3,4,5], [2, 10, 1]))

Answer 4

Die Leistung der @atk-Implementierung für sortierte Arrays von Primitiven kann durch die Verwendung von .pop anstelle von .shift verbessert werden.

function intersect(array1, array2) {
   var result = [];
   // Don't destroy the original arrays
   var a = array1.slice(0);
   var b = array2.slice(0);
   var aLast = a.length - 1;
   var bLast = b.length - 1;
   while (aLast >= 0 && bLast >= 0) {
      if (a[aLast] > b[bLast] ) {
         a.pop();
         aLast--;
      } else if (a[aLast] < b[bLast] ){
         b.pop();
         bLast--;
      } else /* they're equal */ {
         result.push(a.pop());
         b.pop();
         aLast--;
         bLast--;
      }
   }
   return result;
}

Ich habe einen Benchmark mit jsPerf erstellt: http://bit.ly/P9FrZK . Die Verwendung von .pop ist etwa dreimal schneller.

Answer 5

1. Sortieren
2. eine nach der anderen ab dem Index 0 prüfen und daraus ein neues Array erstellen.

Etwas in der Art, allerdings nicht gut getestet.

function intersection(x,y){
 x.sort();y.sort();
 var i=j=0;ret=[];
 while(i<x.length && j<y.length){
  if(x[i]<y[j])i++;
  else if(y[j]<x[i])j++;
  else {
   ret.push(x[i]);
   i++,j++;
  }
 }
 return ret;
}

alert(intersection([1,2,3], [2,3,4,5]));

PS: Der Algorithmus ist nur für Zahlen und normale Zeichenketten gedacht, die Kreuzung beliebiger Objekt-Arrays funktioniert möglicherweise nicht.