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

Verwendung von jQuery :

var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);

Answer 2

Für Arrays, die nur Strings oder Zahlen enthalten, können Sie etwas mit Sortierung tun, wie in einigen der anderen Antworten. Für den allgemeinen Fall von Arrays beliebiger Objekte glaube ich nicht, dass man den langen Weg vermeiden kann. Das Folgende gibt Ihnen die Schnittmenge einer beliebigen Anzahl von Arrays, die als Parameter an arrayIntersection :

var arrayContains = Array.prototype.indexOf ?
    function(arr, val) {
        return arr.indexOf(val) > -1;
    } :
    function(arr, val) {
        var i = arr.length;
        while (i--) {
            if (arr[i] === val) {
                return true;
            }
        }
        return false;
    };

function arrayIntersection() {
    var val, arrayCount, firstArray, i, j, intersection = [], missing;
    var arrays = Array.prototype.slice.call(arguments); // Convert arguments into a real array

    // Search for common values
    firstArray = arrays.pop();
    if (firstArray) {
        j = firstArray.length;
        arrayCount = arrays.length;
        while (j--) {
            val = firstArray[j];
            missing = false;

            // Check val is present in each remaining array 
            i = arrayCount;
            while (!missing && i--) {
                if ( !arrayContains(arrays[i], val) ) {
                    missing = true;
                }
            }
            if (!missing) {
                intersection.push(val);
            }
        }
    }
    return intersection;
}

arrayIntersection( [1, 2, 3, "a"], [1, "a", 2], ["a", 1] ); // Gives [1, "a"];

Answer 3

Eine winzige Änderung der kleinsten hier (die filter/indexOf Lösung ), nämlich die Erstellung eines Index der Werte in einem der Arrays unter Verwendung eines JavaScript-Objekts, wird die Zeit von O(N*M) auf "wahrscheinlich" lineare Zeit reduziert. Quelle1 Quelle2

function intersect(a, b) {
  var aa = {};
  a.forEach(function(v) { aa[v]=1; });
  return b.filter(function(v) { return v in aa; });
}

Dies ist nicht die allereinfachste Lösung (es ist mehr Code als filter+indexOf ), noch ist es das allerschnellste (wahrscheinlich um einen konstanten Faktor langsamer als intersect_safe() ), aber es scheint eine ziemlich gute Balance zu sein. Es ist auf der sehr einfach, aber leistungsfähig und erfordert keine vorsortierten Eingaben.

Answer 4

Ein weiterer indizierter Ansatz, der eine beliebige Anzahl von Arrays gleichzeitig verarbeiten kann:

// Calculate intersection of multiple array or object values.
function intersect (arrList) {
    var arrLength = Object.keys(arrList).length;
        // (Also accepts regular objects as input)
    var index = {};
    for (var i in arrList) {
        for (var j in arrList[i]) {
            var v = arrList[i][j];
            if (index[v] === undefined) index[v] = 0;
            index[v]++;
        };
    };
    var retv = [];
    for (var i in index) {
        if (index[i] == arrLength) retv.push(i);
    };
    return retv;
};

Es funktioniert nur für Werte, die als Strings ausgewertet werden können, und Sie sollten sie als Array übergeben, wie:

intersect ([arr1, arr2, arr3...]);

...aber es akzeptiert transparent Objekte als Parameter oder als eines der zu schneidenden Elemente (und gibt immer ein Array mit gemeinsamen Werten zurück). Beispiele:

intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4]
intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"]

EDIT: Ich habe gerade bemerkt, dass dies in gewisser Weise ein kleiner Fehler ist.

Das heißt: Ich habe es so kodiert, dass ich dachte, dass Eingabefelder selbst keine Wiederholungen enthalten können (wie das Beispiel zeigt, ist das nicht der Fall).

Wenn die Eingabefelder jedoch zufällig Wiederholungen enthalten, würde dies zu falschen Ergebnissen führen. Beispiel (unter Verwendung der folgenden Implementierung):

intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]);
// Expected: [ '1' ]
// Actual: [ '1', '3' ]

Glücklicherweise lässt sich dies leicht beheben, indem einfach eine Indexierung auf zweiter Ebene hinzugefügt wird. Das heißt:

Ändern:

        if (index[v] === undefined) index[v] = 0;
        index[v]++;

von:

        if (index[v] === undefined) index[v] = {};
        index[v][i] = true; // Mark as present in i input.

...und:

         if (index[i] == arrLength) retv.push(i);

von:

         if (Object.keys(index[i]).length == arrLength) retv.push(i);

Vollständiges Beispiel:

// Calculate intersection of multiple array or object values.
function intersect (arrList) {
    var arrLength = Object.keys(arrList).length;
        // (Also accepts regular objects as input)
    var index = {};
    for (var i in arrList) {
        for (var j in arrList[i]) {
            var v = arrList[i][j];
            if (index[v] === undefined) index[v] = {};
            index[v][i] = true; // Mark as present in i input.
        };
    };
    var retv = [];
    for (var i in index) {
        if (Object.keys(index[i]).length == arrLength) retv.push(i);
    };
    return retv;
};

intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // [ '1' ]

Answer 5

Mit einigen Einschränkungen für Ihre Daten können Sie dies in linear Zeit!

Für positive Ganzzahlen : ein Array verwenden, das die Werte auf einen "gesehen/nicht gesehen"-Booleschen Wert abbildet.

function intersectIntegers(array1,array2) { 
   var seen=[],
       result=[];
   for (var i = 0; i < array1.length; i++) {
     seen[array1[i]] = true;
   }
   for (var i = 0; i < array2.length; i++) {
     if ( seen[array2[i]])
        result.push(array2[i]);
   }
   return result;
}

Es gibt eine ähnliche Technik für Objekte : Nehmen Sie einen Dummy-Schlüssel, setzen Sie ihn für jedes Element in array1 auf "true", und suchen Sie dann nach diesem Schlüssel in den Elementen von array2. Bereinigen Sie, wenn Sie fertig sind.

function intersectObjects(array1,array2) { 
   var result=[];
   var key="tmpKey_intersect"
   for (var i = 0; i < array1.length; i++) {
     array1[i][key] = true;
   }
   for (var i = 0; i < array2.length; i++) {
     if (array2[i][key])
        result.push(array2[i]);
   }
   for (var i = 0; i < array1.length; i++) {
     delete array1[i][key];
   }
   return result;
}

Natürlich müssen Sie sich vergewissern, dass der Schlüssel nicht schon vorher vorhanden war, sonst zerstören Sie Ihre Daten...