如何獲得對應於O中的數字的集合（1）

假設有N個數字組合成K個不相交集合。問題是爲這些不相交集合中的每一個創建一個密鑰，使得給定任何數字，對這些密鑰和數字的簡單操作應該能夠給出包含該數字的集合。如何獲得對應於O中的數字的集合（1）

一個簡單的方法，它的侷限性： 例如，讓N個數是34,35,36 ...... .321設套1進行的63,66,77,89,122,222和組2製成的53,69,137,230,280,299,300,306等等..

溶膠： 第一包含（321-34 = 287）項目的素數的數組被創建。爲了爲第一組創建一個鍵，相應於陣列中的位置（63-34），（66-34），...（222-34）的素數被相乘。現在這個鍵只能被對應於集合1中的數字的素數整除，否則不能。所以，給77，[如果（key1％（primeArray [77-34] == 0）]，77屬於set1

但是，由於我處理大量的數據值，鍵不能表示即使64位整數（我不想分裂鍵）。是否有這樣做的更好的辦法？

來源

2013-10-05 user827088

格式是你的朋友btw ... –

位圖不能輕鬆做到這一點嗎？ – Barmar

N和K都很大嗎？如果兩者都很小，則單個散列表映射編號將起作用。如果K很小，那麼K組中的每一組的布隆過濾器可能是一個開始。數字和它們的排列是否完全是任意的，還是有更多的結構可以利用？ – Joe

似乎是一個經典案例使用工會找到的數據結構。 Union-find data structure

給每個在這種情況下，數字本身就是一個數字，在一組中的最高等級代表該組合的數字

來源

2013-10-05 22:06:10 sanz

如何獲得對應於O中的數字的集合（1）

回答

相關問題