我有一组包含整数的集合,数量为N
,假设已经排序并称其为I [1..N]
。给定一个candidate
集合,我需要找到与candidate
存在非空交集的I
子集。
例如,如果:
I = [{1,2}, {2,3}, {4,5}]
我希望定义
valid_items(items, candidate)
,满足以下条件:
valid_items(I, {1}) == {1}
valid_items(I, {2}) == {1, 2}
valid_items(I, {3,4}) == {2, 3}
我正在尝试为给定的一个集合 I
和一个可变的候选集进行优化。目前,我通过缓存 items_containing[n] = {包含 n 的集合}
来实现。在上面的例子中,这将是:
items_containing = [{}, {1}, {1,2}, {2}, {3}, {3}]
即,0不包含在任何项中,1包含在第1个项目中,2包含在第1和第2个项目中,2包含在第2个项目中,3包含在第2个项目中,4和5包含在第3个项目中。
这样,我可以定义
valid_items(I, candidate) = union(items_containing[n] for n in candidate)
。是否有更有效的数据结构(可接受的大小)来缓存此联合的结果?明显的空间
2^N
不可接受,但N
或N * log(N)
是可以接受的。