當集合不相交時，是否有任何與聯合查找相似的交集查找算法？

我想找到包含整數值的集合的交集？如果說你有4-5個2k-4k整數列表，最有效的方法是什麼？當集合不相交時，是否有任何與聯合查找相似的交集查找算法？

2014-02-12 Ajay Bodhe

在Python中你可以使用'set'。 – embert

[線性時間計算集交集？]的可能的副本（http://stackoverflow.com/questions/4642172/computing-set-intersection-in-linear-time） – Dukeling

如果你有記憶騰出：

這是理論上的O（總和所有集合基數+檢索）

其中retrieveal可以是您的整數範圍（如果您使用原始數組）或您的集合的聯合的基數（如果您使用散列表來枚舉定義發生的值）。

如果你的集合的邊界是已知的而且很小，你可以用一個足夠大的整數的簡單數組來實現它（通常是256位的8位字符）。

否則，你需要某種散列表，理論上它應該在o（n）中。

2014-02-12 08:33:58

在許多語言中，例如C++集合被實現爲平衡二叉樹，因此您可以直接在O(NlogM)中評估集合交集，只需查看O(logM)中的其他集合即可。

優化： -

當你想爲多套，你可以做到這一點是huffman coding使用的優化： -

使用的集的優先級隊列，其選擇最小的一套第一個

選擇兩個最小集合首先評估交集並將其添加到隊列中。

這樣做，直到你得到空的交集或剩下一組（交集）。

注：使用std ::設置如果用C++

2014-02-12 09:58:53

回答