Doppelte Array innerhalb Array finden

Question

Bei einem Array von Arrays, was wäre die effiziente Möglichkeit, das doppelte Objekt zu identifizieren?

var array = [ 
    [ 
    11.31866455078125, 
    44.53836644772605 
    ], 
    [      // <-- Here's the duplicate 
    11.31866455078125, 
    44.53836644772605 
    ], 
    [ 
    11.371536254882812, 
    44.53836644772605 
    ], 
    [ 
    11.371536254882812, 
    44.50140292110874 
    ] 
] 

Ich habe mit lodash als akzeptierte Abhängigkeit von dieser Arbeit, und ich bekommen, wie einfach zurück, um die „einzigartige“ -Liste mit _.uniqWith und _.isEqual:

_.uniqWith(array,_.isEqual) 

Mit geben würde, die " einzigartig“-Version der Liste:

[ 
    [ 11.31866455078125, 44.53836644772605 ], 
    [ 11.371536254882812, 44.53836644772605 ], 
    [ 11.371536254882812, 44.50140292110874 ] 
] 

Aber nicht nur die einzigartigen Elemente Berichterstattung, ich brauche das Element nur die dupliziert wird, und im Idealfall t Der Index des ersten Auftretens.

Ist dies tatsächlich in der lodash Bibliothek durch eine Kombination von Methoden, die ich vermisse? Oder muss ich einfach mit Schreibschleifen leben, um Elemente zu vergleichen.

Wahrscheinlich nur übermüdet, also wären neue Augen auf das Problem willkommen.

Der Versuch, nicht Funktionen neu zu schreiben, wenn es Bibliothek Methoden, die Klage, so dass ich im Grunde stecken mit:

1. nur das Duplikat Rückgabe oder zumindest die Vergleichsdifferenz mit der „eindeutige Liste“.

2. Grundsätzlich identifiziert der "Index von" ein Array innerhalb eines Arrays. Obwohl ich denke, dass eine Filterreduktion mit _.isEqual sein kann, sobald das doppelte Element identifiziert wird.

auch versuchen, ein Objekt Hash/Karte zu vermeiden, Erstellen und Zählen das Vorkommens von Schlüsseln auch hier, oder zumindest nicht als separates Objekt, und als etwas, das funktionell „in-line“ durchgeführt werden kann.

Answer 1

Lodash bietet viele nützliche Funktionen, um den ersten doppelten Index zu finden.
Mit dem _.findIndex() und _.isEqual() dem folgenden Code wird den ersten doppelten Index finden:

var duplicateIndex = _.findIndex(array, function(value, index, collection) { 
    var equal = _.isEqual.bind(undefined, value); 
    return _.findIndex(collection.slice(0, index), equal) !== -1; 
}); 

oder ein wenig schneller, aber ausführlicher:

var duplicateIndex = _.findIndex(array, function(value, index, collection) { 
    var equal = _.isEqual.bind(undefined, value); 
    return _.findIndex(collection, function(val, ind) { 
    return ind < index && equal(val); 
    }) !== -1; 
}); 

Beachten Sie, dass, wenn kein Duplikat vorhanden ist, wird -1 zurückgegeben werden .
In wenigen Worten iteriert der Algorithmus durch Array und schaut zurück, ob das aktuelle Element bereits existiert. Wenn dies der Fall ist, geben Sie einfach den aktuellen Iterationsindex zurück.
Bitte überprüfen Sie die funktionierende demo.

Answer 2

Sie können einfach nur ol‘Javascript verwenden zu tun, es ist nicht so schwer, hier ist meine Implementierung

for (var i = 0; i < array.length; i++) { 
    for (var j = i + 1; j < array.length; j++) { 

    // quick elimination by comparing subarray lengths 
    if (array[i].length !== array[j].length) { 
     continue; 
    } 
    // look for dupes 
    var dupe = true; 
    for (var k = 0; k < array[i].length; k++) { 
     if (array[i][k] !== array[j][k]) { 
     dupe = false; 
     break; 
     } 
    } 
    // if a dupe then print 
    if (dupe) { 
     console.debug("%d is a dupe", j); 
    } 
    } 
} 

Das Schöne an dieser Implementierung ist, dass es mehrere Male, dass ein Array gedruckt wird bei Ein Index ist ein Duplikat für mehrere Duplikate, Sie können diese Tatsache verwenden, um Ihre Duplikate in jedem Index zu zählen!

Dies ist eigentlich ein sehr effizienter Weg, dies zu tun, weil die innere for Schleife (j) läuft immer von der nächsten Position der äußeren Schleife (i). Sie zählen also die Hälfte Ihres Schecks.

Und hier ist ein plunk

Answer 3

Ich weiß nicht, wie diese andere zu tun, als nur den Algorithmus selbst zu schreiben. Sowohl diese Antwort und die anderen geschrieben diejenigen sind nicht sehr effizient, aber sollte in Ordnung sein:

function findIndex(array, startingIndex, value) { 
    var predicate = _.partial(_.isEqual, value); 
    var arraySubset = array.slice(startingIndex+1); 
    var index = arraySubset.findIndex(predicate); 
    return index === -1 ? index : index+startingIndex+1; 
} 

function findDuplicates(array) { 
    return array.map((value, index) => { 
    return { 
     value, 
     index: findIndex(array, index, value) 
    }; 
    }).filter(info => info.index !== -1); 
} 

findDuplicates([1, 2, 3, 4, 1, [ 3 ], [ 4 ], [ 3 ] ]); 

// [ { value: 1, index: 4 }, { value: [ 3 ], index: 7 } ] // [ { value: 1, index: 4 }, { value: [ 3 ], index: 7 } ] 

Diese im Grunde eine Karte des Arrays erstellt, ruft .findIndex() auf dem Rest des Feldes, notieren den Index von allen Duplikaten, die Informationen über jedes Element zurückgeben, das ein Duplikat hat und was der Index des Duplikats ist.

Eine schöne Sache ist, dass es für dreifach oder eine beliebige Anzahl von Vorkommen eines Wertes funktioniert.

Answer 4

Hier ist ein Ansatz, der uniqWith() verwendet und difference():

_.indexOf(array, _.head(_.difference(array, _.uniqWith(array, _.isEqual)))); 

Die Grundidee ist:

1. Verwenden uniqWith() die Duplikate von array zu entfernen.
2. Verwenden Sie difference(), um mit der duplikatfreien Version zu vergleichen. Dies bringt uns ein Array der Duplikate.
3. Verwenden Sie head(), um das erste Element des Arrays zu erhalten. Dies ist das Duplikat, an dem wir interessiert sind.
4. Verwenden Sie indexOf(), um den Index des Duplikats zu finden, in diesem Fall ist es 1.

Wenn Sie jedoch den Index des Original benötigen, und nicht ist es duplizieren, haben wir einige Anpassungen vornehmen:

var duplicate = _.head(_.difference(array, _.uniqWith(array, _.isEqual))); 
_.findIndex(array, _.unary(_.partial(_.isEqual, duplicate))); 

Wir sind immer noch uniqWith() verwenden und difference() zu Finde die duplicate. Aber jetzt verwenden wir findIndex(), um den Index zu erhalten. Der Grund ist, dass wir isEqual() verwenden müssen, um die erste Position des Duplikats zu finden, nicht die Sekunde. Wir konstruieren das Prädikat mit partial() und unary(). Das Ergebnis ist diesmal 0.

Answer 5

Ich glaube, das Konstruieren einer LUT ist eine der effizientesten Möglichkeiten, wenn es um Vergleiche geht. Die folgende Methode erstellt eine LUT unter Verwendung von Array.prototype.reduce() und mutiert schließlich das ursprüngliche Array, indem nicht nur ein, sondern alle doppelten Elemente entfernt werden, unabhängig davon, wie viele es sind.

var arr = [ 
 
    [ 
 
    11.31866455078125, 
 
    44.53836644772605 
 
    ], 
 
    [ 
 
    11.31866455078125, 
 
    44.53836644772605 
 
    ], 
 
    [ 
 
    11.371536254882812, 
 
    44.53836644772605 
 
    ], 
 
    [ 
 
    11.371536254882812, 
 
    44.50140292110874 
 
    ] 
 
]; 
 
arr.reduce((p,c,i)=> { var prop = c[0]+"" + c[1]+""; 
 
         p[prop] === void 0 ? p[prop] = i : p.dups.push(i); 
 
         return p; 
 
        },{dups:[]}).dups.reverse().forEach(i => arr.splice(i,1)) 
 

 
document.write('<pre>' + JSON.stringify(arr, 0, 2) + '</pre>');

Allerdings, wenn Sie das Original, indem sie dann offensichtlich wäre es viel schnelle Prozedur ein neues Array haben möge.