檢查兩個數字列表是否相等

給定兩個數字列表A，B。有沒有更好的方法來檢查它們是否等於O（N^2）解決方案。檢查兩個數字列表是否相等

2012-07-04 algo_freek

定義「相等」。同樣的順序？重複的元素？ – SLaks

你的意思是'有沒有更好的方法來檢查它們是否包含相同的數字？'在我的書籍清單中，平等要求數字都是相同的，並且我認爲需要O（n）操作來檢查相同的順序。 –

列表的任何特殊特徵？他們排序了嗎？數字是否有界？另外，您是否允許使用非恆定數量的額外內存？ – Jon

如果你的意思是，這兩個列表包含相同的數字，沒有對於排序，你可以使用以下O(n *log n)算法：

步驟（1）需要2 * O(n *log n) = O(n *log n)時間。第二步以線性O(n)時間運行。

因此運行上述算法可以在O(n *log n)時間內解決您的問題。

2012-07-04 14:23:50 Sirko

如果數字是整數，則可以使用具有O（n）時間複雜度的桶分類算法（更精確地說，時間複雜度是O（n + r），其中r是數字範圍），將問題減少到O （n）+ O（n）+ O（n）= O（n）複雜度 –

或'O（n * log（r））'的二進制基數排序，此時'r'是最大可表示值超過實際存在的最大值。它可以做到位，這很好。 –

假設數字在列表上的排序，並且兩個列表具有相同的長度：

bool eq = true; 

for (int i = 0; i < list1.length; i++) { 
    if (list1[i] != list2[i]) { 
     eq = false; 
     last; 
    } 
}

2012-07-04 14:24:04 Ruel

首先檢查，如果他們有相同的長度。如果是，你可以把A的數字放在HashSet中。通過B迭代並檢查它是否存在於HashSet中。如果它在那裏，你可以從HashSet中移除。如果最後HashSet是空的，它們是相等的。這是O（n）

實際上，HashSet中不允許有重複項，因此您可以使用帶有鍵的HashMap作爲數字和值作爲計數。算法保持不變。每次在HashMap遞減計數中找到多個B.如果最後HashMap是空的，那麼它們是相等的。這也是O（n）。

2012-07-04 14:24:36 user1168577

謝謝。我也想出了O（n * logn）算法，但我喜歡Urs！ –

謝謝。我也喜歡這個：）。如果你能接受的話，它會有所幫助（再次只在你喜歡它的時候:)）我的回答特別是因爲（令人驚訝的）沒有人贊成我的:)。 – user1168577

排序2所列出O（nlogn）
然後在他們兩人同時去看看它們包含了相同的數字爲O（n）

總：O（nlogn）

2012-07-04 14:24:44

回答