※ 引述《chunhsiang (= =)》之銘言：
: 假設集合A與B作交集 n=|A| m=|B|
: 只需要O(n+m)
推 EdisonX:我想到用 bitwise...這效率應該是超高,不過會受限就是了. 10/02 22:54
→ chunhsiang:您是說將原本的set轉為01的型式再作運算? 但宇集很大 10/02 22:59
推 EdisonX:bitwise 在意的是,set 是否為整數,及其最大、最小值 10/02 23:00
回文說明較清楚。虛碼部份以 C 大致示之。
假設 A = {200,-1,2,100}, B={-100,-1,200,2}, 不一定要照順序
(1) 先掃 A, B 一遍，紀錄整體最大、最小值，Max, Min (200, -100)
(2) 如果每個數字都用一個位元表示的話，需要 Max - Min + 1 = 301 bits
假設一個無號數 (unsigned int ) 佔了 32 bits ，可計算出，
需要陣列的大小約是 301 / 32 + 1 = 10 <不考慮剛好是32整數bit問題>
unsigned ASet[10]={0U}, BSet[10]={0U};
unsigned idx; /*這用來計算到時候放在陣列哪個 idx*/
unsigned bit; /*這用來計算到時候放在陣列哪個 bit*/
(3) 先 polling A, B
(3.1) 紀錄 200 : 200-Min=300, idx=300/32 = 9, bit = 300%32=12
ASet[idx] |= (1U<<bit);
(3.2) 紀錄 -1 : -1-Min=99, idx=99/32 = 3, bit =99%32=3
ASet[idx] |= (1U<<bit);
....
(4) 計算結果 unsigned Rst[10];
for(i=0; i<10; ++i) Rst[i] = ASet[i] & BSet[i];
最後要輸出的時候再根據 Rst 內容做輸出。
(1) : O(n+m)
(2) : O(1)
(3) : O(n+m)
(4) : O(n+m)
整體應該還算 O(n+m) <吧？>
但如上所見，有幾個缺點
(1) 只適用整數集合
(2) Max-Min 過大的時候就浪費記憶體 <情況不要太偏激的話，記憶體應都還堪用>
非整數、稀疏、範圍大時，可能就不適用。
不知您的情況是？？

有出現的再安排位置就好啦

disjoint set + union by rank + path compression有optimal solution in linear time 喔!可以google 一下

所以說運算先後順序不重要?disjoint set是集合間都不會有一樣的元素 與全部交集有何關係... 恕我愚昧一問...能不能白話點...