如何從n個數組中找到公共元素

Question

我在考慮排序然後進行二分搜索。這是最好的方法嗎？

Answer 1

我在這種情況下主張散列：您將有時間與兩個數組的常見大小成比例。
由於大多數主要語言都在其標準庫中提供散列表，我幾乎不需要展示如何實現這樣的解決方案。

Answer 2

定義「最佳」。

如果你想快速做到這一點，你可以通過遍歷每個數組並保持每個唯一元素的計數來完成O（n）操作。如何計算獨特元素的細節取決於數組中可能存在的事物的字母表，例如它是稀疏還是密集的？

注意，這是在陣列的數目爲O（n），但O（納米）爲長度米）的陣列。

Answer 3

遍歷每一個並使用散列表來存儲計數。關鍵是整數值，值是出現次數。

Answer 4

這取決於。如果一個集合比另一個要小得多，或者由於某種其他原因，你期望交集非常稀疏，那麼二分查找可能是合理的。否則，可能最容易一次完成兩個步驟。如果一箇中的當前元素小於另一箇中的元素，則前進到該數組中的下一個項目。當/如果得到相同的元素，則將其作爲輸出發送，然後前進到兩個數組中的下一個項目。 （這個假設，就像你所倡導的那樣，當然你已經對這兩者進行了排序）。

這是一個O（N + M）操作，其中N是一個數組的大小，M是另一個的大小。使用二進制搜索，您可以獲得O（N lg M），如果一個數組比另一個數組小，可能會降低複雜性，但如果它們接近相同大小，則可能會造成淨損失。

根據您需要/想要的版本，試圖計算出現次數的版本可能會導致相當大的問題：如果在一個數組中出現多次單個項目，它們仍會將此次數計爲兩次項目，表明一個並不存在的交集。您可以防止這種情況，但這樣做會使作業稍微不重要 - 您將一個數組中的項插入到散列表中，但始終將計數設置爲1.完成後，通過將計數設置爲2來處理第二個數組當且僅當該項目已經存在於該表格中時。

Answer 5

最好的方法是哈希所有的值並保持發生次數，剔除所有沒有發生的事情i次當您檢查數組i其中i = {1, 2, ..., n}。不幸的是，沒有確定性算法可以讓你的運行時間小於O(n*m)，因爲如果不排除所有數組中的所有值，就不可能做到這一點。

一個更快的算法需要有一個可接受的概率水平（蒙特卡洛），或者依靠一些已知的列表條件來檢查只有一部分元素（即你只關心所有發生在i-1以前的列表在考慮i列表時，但在未排序的列表中，搜索元素並不重要。