Znajdź duplikat macierzy wewnątrz tablicy

Question

Jaki jest skuteczny sposób identyfikowania zduplikowanego elementu w postaci tablicy tablic?

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

Pracuję nad tym z lodash jako zaakceptowanej uzależnienia i uzyskać jak tylko zwrotu „unikalne” listy używając _.uniqWith i _.isEqual:

_.uniqWith(array,_.isEqual) 

Z dałoby " unikalna "wersja listy:

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

Ale zamiast tylko zgłaszać unikalne elementy, potrzebuję tylko elementu, który jest duplikowany, i idealnie t indeks pierwszego wystąpienia.

Czy jest to faktycznie uwzględnione w bibliotece lodash za pomocą jakiejś kombinacji metod, których mi brakuje? Czy po prostu będę musiał żyć z pisaniem pętli do porównywania elementów.

Prawdopodobnie tylko przemęczony tym, więc świeże spojrzenie na problem byłoby mile widziane.

starając się nie przepisać funkcje jeśli istnieją metody biblioteki, które pasować, tak ja w zasadzie jestem zatrzymany z:

1. Wracając tylko duplikat lub przynajmniej różnicę porównania z listy „unikalny”.

2. Zasadniczo identyfikując "indeks" tablicy w tablicy. Chociaż przypuszczam, że może to być zmniejszenie filtru z _.isEqual po zidentyfikowaniu zduplikowanego elementu.

Próbuje również w celu uniknięcia tworzenia obiektu Hash/MAP i zliczanie wystąpień kluczy tutaj jak dobrze, albo przynajmniej nie jako odrębny przedmiot, a jako coś, co można zrobić funkcjonalnie „in-line”.

Answer 1

Lodash daje wiele przydatnych funkcji, aby znaleźć pierwszy zduplikowany indeks.
Używanie _.findIndex() i _.isEqual() następujący kod znajdzie pierwszy duplikat index:

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

lub nieco szybciej, ale bardziej opisowy:

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; 
}); 

Zauważ, że jeśli nie duplikat istnieje, zostanie zwrócony -1 .
W kilku słowach algorytm iteruje poprzez tablicę i sprawdza, czy bieżący element już nie istnieje. Jeśli tak, po prostu zwróć bieżący indeks iteracji.
Proszę sprawdzić działający demo.

Answer 2

można po prostu użyć zwykły ol”javascript, aby to zrobić, to nie jest takie trudne, tutaj jest moja realizacja

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); 
    } 
    } 
} 

Miłą część o tej realizacji jest to, że drukowanie ci wiele razy, że tablica na Indeks jest dupkiem dla wielokrotnych dupków, możesz użyć tego faktu, aby policzyć swoje duplikaty w każdym indeksie!

Jest to bardzo skuteczny sposób, aby to zrobić, ponieważ wewnętrzna pętla for (j) zawsze przebiega od następnej pozycji zewnętrznej pętli (i). więc połowa twojego czeku się liczy.

A oto plunk

Answer 3

nie wiem jak to zrobić, inne niż po prostu napisać algorytm siebie. Zarówno ta odpowiedź i pozostali pisał te nie są bardzo skuteczne, ale powinno być dobrze:

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 } ] 

To w zasadzie tworzy mapę tablicy, nazywając .findIndex() na pozostałej części tablicy, notując indeksu wszelkich duplikatów, zwracanie informacji o każdym egzemplarzu, który ma duplikat i jaki jest indeks duplikatu.

Jedną dobrą rzeczą jest to, że zadziała w trzech powtórzeniach lub dowolnych ilościach wartości.

Answer 4

Oto podejście, które wykorzystuje uniqWith() i difference():

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

Podstawowym założeniem jest:

1. Zastosowanie uniqWith() usunąć duplikaty z array.
2. Użyj difference(), aby porównać z wersją bez duplikatów. Daje nam to zestaw duplikatów.
3. Użyj head(), aby uzyskać pierwszy element tablicy. To jest duplikat, który nas interesuje.
4. Użyj indexOf(), aby znaleźć indeks duplikatu, w tym przypadku jest to 1.

Jednak jeśli trzeba indeks oryginalnym, i nie jest to powielać, musimy dokonać pewnych korekt:

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

Ciągle użyciu uniqWith() i difference() do znajdź duplicate. Ale teraz używamy findIndex(), aby uzyskać indeks. Powodem jest to, że musimy użyć isEqual(), aby znaleźć pozycję najpierw duplikatu, a nie sekundę. Konstruujemy predykat za pomocą partial() i unary(). Rezultatem tym razem jest 0.

Answer 5

Uważam, że skonstruowanie LUT jest jednym z najskuteczniejszych sposobów dokonywania porównań. Następująca metoda konstruuje LUT przez wykorzystanie Array.prototype.reduce() i ostatecznie mutuje oryginalną macierz przez usunięcie nie tylko jednego, ale wszystkich zduplikowanych elementów, niezależnie od tego, ile istnieje.

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>');

Jednak jeśli chcesz mieć nową tablicę zachowując oryginalny to oczywiście byłoby znacznie szybciej procedura.