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

Ein funktionaler Ansatz mit ES2015

Bei einem funktionalen Ansatz dürfen nur reine Funktionen ohne Seiteneffekte verwendet werden, die jeweils nur mit einer einzigen Aufgabe befasst sind.

Diese Einschränkungen verbessern die Kompositionsfähigkeit und Wiederverwendbarkeit der beteiligten Funktionen.

// small, reusable auxiliary functions

const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const apply = f => x => f(x);

// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};

// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];

// run it

console.log( intersect(xs) (ys) );

Bitte beachten Sie, dass der native Set Typ verwendet, der den Vorteil hat, dass er Nachschlageleistung hat.

Vermeiden Sie Duplikate

Offensichtlich wiederholt auftretende Elemente aus dem ersten Array erhalten bleiben, während die zweite Array wird de-dupliziert. Dies kann das gewünschte Verhalten sein oder auch nicht. Wenn Sie ein eindeutiges Ergebnis benötigen, wenden Sie einfach dedupe zum ersten Argument:

// auxiliary functions

const apply = f => x => f(x);
const comp = f => g => x => f(g(x));
const afrom = apply(Array.from);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));

// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};

// de-duplication

const dedupe = comp(afrom) (createSet);

// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];

// unique result

console.log( intersect(dedupe(xs)) (ys) );

Berechnen Sie die Schnittmenge einer beliebigen Anzahl von Array s

Wenn Sie die Schnittmenge einer beliebigen Anzahl von Array s einfach komponieren intersect con foldl . Hier ist eine Komfortfunktion:

// auxiliary functions

const apply = f => x => f(x);
const uncurry = f => (x, y) => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const foldl = f => acc => xs => xs.reduce(uncurry(f), acc);

// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};

// intersection of an arbitrarily number of Arrays

const intersectn = (head, ...tail) => foldl(intersect) (head) (tail);

// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
const zs = [0,1,2,3,4,5,6];

// run

console.log( intersectn(xs, ys, zs) );

Answer 2

.reduce um eine Karte zu erstellen, und .filter um den Schnittpunkt zu finden. delete innerhalb der .filter ermöglicht es uns, das zweite Array so zu behandeln, als ob es eine eindeutige Menge wäre.

function intersection (a, b) {
  var seen = a.reduce(function (h, k) {
    h[k] = true;
    return h;
  }, {});

  return b.filter(function (k) {
    var exists = seen[k];
    delete seen[k];
    return exists;
  });
}

Ich finde diesen Ansatz ziemlich einfach zu begründen. Er wird in konstanter Zeit ausgeführt.

Answer 3

Ich verwende eine Karte, auch ein Objekt kann verwendet werden.

//find intersection of 2 arrs
const intersections = (arr1,arr2) => {
  let arrf = arr1.concat(arr2)
  let map = new Map();
  let union = [];
  for(let i=0; i<arrf.length; i++){
    if(map.get(arrf[i])){
      map.set(arrf[i],false);
    }else{
      map.set(arrf[i],true);
    }
  }
 map.forEach((v,k)=>{if(!v){union.push(k);}})
 return union;
}

Answer 4

Ich denke, die interne Verwendung eines Objekts kann bei Berechnungen helfen und könnte auch performant sein.

// Ansatz behält eine Zählung jedes Elements bei und funktioniert auch bei negativen Elementen

function intersect(a,b){

    const A = {};
    a.forEach((v)=>{A[v] ? ++A[v] : A[v] = 1});
    const B = {};
    b.forEach((v)=>{B[v] ? ++B[v] : B[v] = 1});
    const C = {};
    Object.entries(A).map((x)=>C[x[0]] = Math.min(x[1],B[x[0]]))
    return Object.entries(C).map((x)=>Array(x[1]).fill(Number(x[0]))).flat();
}
const x = [1,1,-1,-1,0,0,2,2];
const y = [2,0,1,1,1,1,0,-1,-1,-1];
const result = intersect(x,y);
console.log(result);  // (7) [0, 0, 1, 1, 2, -1, -1]

Answer 5

Erstellen eines Objekts mit einem Array und Durchlaufen des zweiten Arrays, um zu prüfen, ob der Wert als Schlüssel existiert.

function intersection(arr1, arr2) {
  var myObj = {};
  var myArr = [];
  for (var i = 0, len = arr1.length; i < len; i += 1) {
    if(myObj[arr1[i]]) {
      myObj[arr1[i]] += 1; 
    } else {
      myObj[arr1[i]] = 1;
    }
  }
  for (var j = 0, len = arr2.length; j < len; j += 1) {
    if(myObj[arr2[j]] && myArr.indexOf(arr2[j]) === -1) {
      myArr.push(arr2[j]);
    }
  }
  return myArr;
}