范围交叉是一个简单但非平凡的问题.
已经回答了两次:
第一个解决方案是O(n),第二个解决方案是数据库(当然小于O(n)).
我有同样的问题,但对于一个大的n,我不在数据库中.
这个问题似乎与存储2D点非常相似,可以快速检索矩形内的那些,但我看不到它是如何映射的.
那么你将数据结构存储在哪个数据结构中,以便搜索范围的成本低于O(n)？(使用可用于Java的库的额外功劳)
编辑:
我想获得所有相交范围的子集,这意味着搜索范围可以与多个范围相交.
Java中需要小于O(n)的方法是:
public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}
其中Range只是一个包含一对int start和end的类.
这不是一个不可能的问题,我已经有了解决方案,我只是想看看是否有更标准/更简单的方法
什么是以紧凑和快速的方式表示稀疏整数集(真正的C内存地址)的好方法.我已经知道像位向量和行程编码这样的显而易见的事情了.但我想要比每组元素一个词更紧凑的东西.我需要添加和删除元素并测试成员资格.我不需要其他的集合操作,比如union.
多年前我读过一个这样的图书馆,但后来忘记了它的名字.我认为它是由HP发布的,并且有一个女人的名字.
我有一组uint32整数,集合中可能有数百万个项目.其中50-70%是连续的,但在输入流中它们以不可预测的顺序出现.
我需要:
将此集合压缩到范围内以实现空间有效表示.已经使用普通算法实现了这一点,因为只计算一次速度的范围在这里并不重要.在此转换之后,所得范围的数量通常在5 000-10 000之间,当然,其中许多是单项.
测试某些整数的成员资格,不需要有关集合中特定范围的信息.这个必须非常快 - O(1).正在考虑最小的完美哈希函数,但它们不能很好地适应范围.位集空间效率很低.其他结构,如二叉树,具有O(log n)的复杂性,最糟糕的是它们实现了许多条件跳转,而处理器无法很好地预测它们,从而导致性能不佳.
是否有专门用于整数范围的数据结构或算法来解决此任务？
我有一个带整数值的区间列表[例如.[1,4],[10,19]等].有没有办法将这些间隔放入一些java集合的容器中[例如.设置]这样我就可以在容器上调用'union'函数.'union'函数应该给我一个间隔列表,这样如果任何2个插入的间隔重叠,那么它们应该在输出中合并.我尝试在Guava中使用Range类,但最终在合并之前将所有间隔相互比较.一个优雅的方法将非常感谢!以下是我根据以下回答尝试的内容.输出为[[1,15],[17,20]],这是正确的.我想知道是否有一些现有的API实现了这样的东西.
public static void main(String[] args) {
// mock data
List<MyIntRange> rng_lst = new ArrayList<Junk.MyIntRange>();
rng_lst.add(new MyIntRange(1, 10));
rng_lst.add(new MyIntRange(5, 15));
rng_lst.add(new MyIntRange(17, 20));
// sort intervals by start position
Collections.sort(rng_lst);
// merge the intervals which overlap
List<MyIntRange> res_lst = new ArrayList<Junk.MyIntRange>();
MyIntRange old_rng = null;
for (MyIntRange cur_rng : rng_lst) {
if (old_rng == null) {
old_rng = cur_rng;
} else {
if (old_rng.rng.upperEndpoint() < cur_rng.rng.lowerEndpoint()) {
// this does not over lap with the next one
res_lst.add(old_rng);
old_rng …