在數組中找到重複數組

Question

給定一個數組數組，那麼識別重複項的有效方法是什麼？

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

我一直對這個有lodash爲接受的依賴，我也得到了如何使用_.uniqWith和_.isEqual剛剛回歸的「獨一無二」的文章：

_.uniqWith(array,_.isEqual) 

隨着會給「獨特的」版本列表：

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

但是，而不是僅僅報告獨特的元素，我需要的只是被複制的元素，非常牛逼他是第一次出現的索引。

這實際上是由lodash圖書館通過一些我缺少的方法組合來覆蓋的嗎？或者我只是需要通過編寫循環來比較元素。

對此可能只是過於樂觀，對這個問題如此清晰的目光是值得歡迎的。

儘量不如果有庫方法那件衣服，所以我基本上是卡與重寫功能：

1. 只返回重複或至少比較差的「唯一列表」。

2. 基本上確定數組中的「索引」。雖然我想這可以通過_.isEqual一旦找到重複項目就可以減少過濾器。

也試圖避免創建對象的哈希/地圖和計數這裏以及按鍵的出現，或者至少不是作爲一個單獨的對象，並作爲東西，可以「在線」功能來完成。

Answer 1

Lodash提供了很多有用的功能來實現找到第一個重複索引。
使用_.findIndex()和_.isEqual()下面的代碼會發現第一個重複的指標：

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

或快一點，但更詳細：

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

注意，如果不存在重複，-1將被退回。
簡而言之，該算法遍歷數組，並返回當前元素是否已經存在。如果是這樣，只需返回當前的迭代索引。請致電demo。

Answer 2

你可以只使用純醇」 JavaScript來做到這一點，並不難，這裏是我的執行

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

關於這個實現的好處是，它會多次打印您的數組中一個指數是一個愚蠢的多重愚蠢，你可以用這個事實來計算你的愚蠢在每個指數！

這實際上是一種非常有效的方法，因爲內部for循環（j）總是從外部循環的下一個位置（i）運行。所以你支票的一半。

這裏是一個plunk

Answer 3

我不知道該怎麼做，而不是隻寫自己的算法，這個其他。無論這個答案，另一個貼的人都不是很有效的，但應罰款：

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

這基本上創建地圖的數組，對數組的剩餘部分調用.findIndex（），並指出了指數的任何重複項，返回有關每個重複項的信息以及重複項的索引。

這樣做的一個好處是它可以工作三次或任意數量的值。

Answer 4

下面是一個使用uniqWith()和difference()的方法：

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

的基本思路是：

1. 使用uniqWith()從array刪除重複。
2. 使用difference()將array與免費版本進行比較。這讓我們得到了重複數組。使用head()獲取數組的第一項。這是我們感興趣的副本。
3. 使用indexOf()可以找到副本的索引，在這種情況下，它的格式爲1。

但是，如果你需要的原的指標，而不是它的複製，我們必須做一些調整：

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

我們仍然使用uniqWith()，並difference()到找到duplicate。但是現在，我們使用findIndex()來獲取索引。原因是我們需要用isEqual()找到第一個位置的重複，而不是第二個。我們使用partial()和unary()構造謂詞。這次的結果是0。

Answer 5

我相信構建LUT是進行比較時最有效的方法之一。以下方法通過利用Array.prototype.reduce()構造LUT，並最終通過刪除不僅一個而是全部重複元素而使原始數組發生變異，而不管其中有多少元素。

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

但是，如果你想通過保持原來的那顯然會更快的程序有一個新的陣列。