JavaScript：刪除數組數組中的重複項

當前使用JavaScript，我需要通過數組數組來確定是否存在任何重複數組，然後刪除這些重複數組。在這種情況下，運行時是至關重要的，所以我想知道做這件事最有效的方法是什麼。JavaScript：刪除數組數組中的重複項

在這種情況下是否使用了一個散列表？這個範圍將是散列每個序列，然後使用散列來確定該序列是否再次發生。因此，每個序列都是主數組中的數組，任何重複數據都是同一數組中的其他數組。此外，所有單個陣列自己保持有序（即單個陣列中的元素必須始終保持其位置）是非常重要的。此外，單個數組中的所有元素都是字符串值。

示例：假定有一個數組A其元素反過來以下的數組：

A[0] = ["one", "two", "three", "four"] 
A[1] = ["two", "one", "three", "four"] 
A[2] = ["one", "two", "three", "four"]

在上述例子中，A [0]和A [2]是重複並且因此函數應該返回A [0]和A [1]，這樣只有一個同一個數組的實例。

來源

2014-10-08 Katia Abela

好問題，但你的嘗試在哪裏？ – 2014-10-08 15:16:14

想知道實現之前理想的解決方案是什麼，因爲時間複雜性是至關重要的。 – 2014-10-08 15:19:37

這裏的效率有兩個含義：如果編碼最快的算法需要一天，但你只是檢查100個數組，我不確定這是否有效。也許雙'for'循環就夠了。 A和A [n]的大小是多少？ – 2014-10-08 15:23:03

保留一個對象，其中的鍵是每個數組的連接元素。如果找不到密鑰，則將數組添加到輸出數組並將該密鑰添加到該對象。

var hash = {}; 
var out = []; 
for (var i = 0, l = A.length; i < l; i++) { 
    var key = A[i].join('|'); 
    if (!hash[key]) { 
    out.push(A[i]); 
    hash[key] = 'found'; 
    } 
}

DEMO

來源

2014-10-08 15:42:05 Andy

我會建議使用不同的「連接」字符。理想情況下，它應該是在輸入數組的字符串中找不到的。如果它應該適用於使用'JSON.stringify'的任何輸入是一個選項。 – Prusse 2014-10-08 15:45:12

'['foo'，'bar']'與['foobar']'不一樣，但在您的解決方案中，它們將被視爲相等。 – 2014-10-08 15:51:41

斑點。我選擇了'|'。 – Andy 2014-10-08 15:56:40

好吧，讓我們先來看看天真的解決方案的複雜性：如果有n個陣列，每個至多爲k項，你需要O(n^2 * k)比較，因爲每個這n個數組，你必須將它與n-1個其他數據進行k次比較。空間複雜度是O(n*k)

所以，如果你願意爲更好的性能平衡的空間，你可以做到以下幾點：（短免責聲明：我假設你所有的陣列具有其被指示，但沒有批准k個元素相同數量的你的問題。）

一個接一個地通過陣列，你選擇第一個元素，我們假設是a。使用哈希映射來驗證您之前是否將此元素視爲第一個元素。如果不是，創建一個以a作爲其根的樹結構，將其存儲在您的哈希映射中的a下，並使其成爲您的當前節點。現在，對於當前數組中的每個後續條目，檢查當前節點是否具有此類子節點。因此，如果第二個條目是b，則您將b添加爲a的子項。

你的樹，現在看起來像這樣：（從左到右依次爲：根兒童）

一個 - B

有c作爲第三項的工作方式完全相同：

A - B - c

現在我們跳過去看一看數組[a, c, d]。您首先遇到元素a的樹。對於第二個元素，您檢查c是否已經是a的子項。如果沒有，添加它：

- b - c 
a 
    - c

同樣適用於下一個條目：

- b - c 
a 
    - c - d

現在讓我們看看，當我們檢查，我們看到了一個陣列發生什麼事之前：[a, b, c]

首先，我們檢查a，看到已經有一棵樹並從哈希映射中獲取它。接下來，我們注意到a有一個名爲b的孩子，所以我們下降到b。現在，對於最後一個條目，我們看到它已經在那裏，告訴我們我們遇到了一個我們可以放棄的副本。

對於即興創作的圖畫，我希望我能把想法貫穿始終。它只是通過每個數組只存儲一次，以非冗餘方式存儲它。所以時間複雜度將是O(n*k)。已使用的空間增加但受到O(n*k)的限制，因爲最壞的情況是沒有數組共享任何前綴，這導致相同的空間複雜度。

希望我沒有忽略一些東西。

來源

2014-10-08 16:31:05 user3363866

感謝您的輸入。使用樹結構去實現它實際上並沒有超出我的想法。這就是說，並不是所有的數組都有相同數量的元素。 – 2014-10-11 12:13:42

不客氣。那麼，我的方法不再工作了，因爲你不能區分路徑的前綴是否遇到過...... – user3363866 2014-10-11 12:44:28

JavaScript：刪除數組數組中的重複項

回答

相關問題