※ 引述《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 过大的时候就浪费内存 <情况不要太偏激的话，内存应都还堪用>
非整数、稀疏、范围大时，可能就不适用。
不知您的情况是？？