作者EdisonX (闭上眼的鱼)
站内Prob_Solve
标题Re: [问题] 多个set作交集
时间Tue Oct 2 23:23:28 2012
※ 引述《chunhsiang (= =)》之铭言：
: 假设集合A与B作交集 n=|A| m=|B|
: 只需要O(n+m)
1F：推 EdisonX:我想到用 bitwise...这效率应该是超高,不过会受限就是了.10/02 22:54
2F：→ chunhsiang:您是说将原本的set转为01的型式再作运算? 但宇集很大10/02 22:59
3F：推 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 过大的时候就浪费记忆体 <情况不要太偏激的话，记忆体应都还堪用>
非整数、稀疏、范围大时，可能就不适用。
不知您的情况是？？
--
「自从我学了 C# , 人都变聪明 , 考试都考一百分」
「自从我学了 VB , 皮肤都变好 , 人也变漂亮了 」
「自从我学了 Java , 明显变壮 , 个子也变高了 」
「自从我学了 C++ , 内分泌失调 , 头都秃了... 」
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 180.177.76.161
※ 编辑: EdisonX 来自: 180.177.76.161 (10/02 23:28)
4F：推 ledia:有出现的再安排位置就好啦 10/03 00:36
5F：推 singlovesong:disjoint set + union by rank + path compression 10/03 11:44
6F：→ singlovesong:有optimal solution in linear time 喔! 10/03 11:44
7F：→ singlovesong:可以google 一下 10/03 11:44
8F：→ chunhsiang:所以说运算先後顺序不重要? 10/03 15:09
9F：→ chunhsiang:disjoint set是集合间都不会有一样的元素 与全部交集 10/03 15:17
10F：→ chunhsiang:有何关系... 恕我愚昧一问...能不能白话点... 10/03 15:19