我有一个代表 range 类的对象列表,例如
public class Range
{
int upperValue;
int lowerValue
}
然后我有
List<Range> ranges=new ArrayList<>();
在用值填充此列表之后或同时,我想检查插入的每个新范围是否与列表中以前的值相交。
例如,如果我有
[1,4]
[2,4]
[3,5]
我想检测 [3,5] 与 [1,4] 和 [2,4] 相交
并且 [2,4] 与 [1,4] 相交
所以我设法做但效率不高的是:
首先,我使用比较器按较低值对列表进行排序。
然后我在排序后再次循环到列表中,并从列表中的第二个元素开始检查它是否与列表中的所有先前元素相交,例如以相反的方式循环。
类似这样的事情
Map<Range,List<Range>> rangeIntersectionMap=new HashMap<>();
for(int i=0;i<ranges.size();i++)
{
if(i>0)
{
List<Range> intersections= rangeIntersectionMap.get(ranges.get(i));
if(intersections==null)
intersections=new ArrayList<>();
for(int j=i-1;j>0;j--)
{
if(checkIntersection(ranges.get(i),ranges.get(j))
{
intersections.add(ranges.get(j));
}
}
rangeIntersectionMap.put(ranges.get(i),intersections);
}
}
这可能意味着,如果我有一个包含 20 个元素的列表,我需要阶乘时间复杂度来检查哪些元素彼此相交。
我认为 NavigableMap 可以解决这个问题,但是我无法正确使用它来实现此目的。
还有其他建议的数据结构或算法吗?
最佳答案
有Interval Search Tree此类问题的结构。
想法是:
- 每个节点代表区间,将两个端点保存在一个节点中
- 在每个节点中保存其子树的最大(右)端点值
- 搜索关键字是两者中较小的值
插入:
- 使用低值来导航插入
- 相应地更新子树中的最大值
搜索:
- 如果节点中的区间与查询区间相交,则返回
- 如果左子树为空,则向右走
- 否则如果左子树中的最大值小于搜索到的低值,则向右走
- 否则向左走
您可以查看这个video和 implementation由 Sedgewick 教授和 Kevin Wayne 教授详细解释。
关于Java 检查列表中范围内每个元素的交集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43518243/