Java中的范围查找

Question

假设,我有一个未排序的重叠数组ranges.每个range只是一对整数begin和end.现在我想找出一个给定是否key属于至少一个ranges.也许,我必须知道ranges它也属于它.

我们可以假设ranges数组需要大约1M并且适合内存.我正在寻找一种简单的算法,它只使用标准的JDK集合,没有任何3d派对库和特殊的数据结构,但工作速度相当快.

你会建议什么？

Answer 1

用自定义数字地对范围进行排序Comparator,然后为每个键k构建一个单元素范围[ k,k ],并用不同的方式对该范围进行二进制搜索Comparator.

在Comparator搜索的compare(x,y)应该返回

• <0 如果 x.max < y.min
• >0 如果 x.min > y.max
• 0 否则(它的两个范围参数重叠).

正如@Per所说,你需要一个不同的,更严格Comparator的排序,但前两个条款仍然有效.

即使范围重叠,这也应该有效,但您可能希望在排序后合并重叠范围以加快搜索速度.合并可以在O(N)时间内完成.

这实际上是静态间隔树,即没有O(lg N)插入或删除的静态间隔树,其方式与排序的数组可以被认为是静态二进制搜索树的方式相同.

Answer 2

如果您不需要知道哪个间隔包含您的观点（编辑：我想您可能知道，但我会将这个答案留给其他不知道这个问题的人），那么

\n\n

\n

1. 通过计算两个数组 B 和 E 来预处理间隔。B 是按排序顺序排列的 begin 值。E 是按排序顺序排列的 end 值。

\n

2. 要查询点 x，请使用二分查找找到满足 B[i] > x 的最小索引 i 和满足 E[j] \xe2\x89\xa5 x 的最小索引 j。包含 x 的区间 [begin, end] 的数量为 i - j。

\n

\n\n\n\n

class Interval {\n    double begin, end;\n}\n\nclass BeginComparator implements java.util.Comparator<Interval> {\n    public int compare(Interval o1, Interval o2) {\n        return Double.compare(o1.begin, o2.begin);\n    }\n};\n\npublic class IntervalTree {\n    IntervalTree(Interval[] intervals_) {\n        intervals = intervals_.clone();\n        java.util.Arrays.sort(intervals, new BeginComparator());\n        maxEnd = new double[intervals.length];\n        initializeMaxEnd(0, intervals.length);\n    }\n\n    double initializeMaxEnd(int a, int b) {\n        if (a >= b) {\n            return Double.NEGATIVE_INFINITY;\n        }\n        int m = (a + b) >>> 1;\n        maxEnd[m] = initializeMaxEnd(a, m);\n        return Math.max(Math.max(maxEnd[m], intervals[m].end), initializeMaxEnd(m + 1, b));\n    }\n\n    void findContainingIntervals(double x, int a, int b, java.util.Collection<Interval> result) {\n        if (a >= b) {\n            return;\n        }\n        int m = (a + b) >>> 1;\n        Interval i = intervals[m];\n        if (x < i.begin) {\n            findContainingIntervals(x, a, m, result);\n        } else {\n            if (x <= i.end) {\n                result.add(i);\n            }\n            if (maxEnd[m] >= x) {\n                findContainingIntervals(x, a, m, result);\n            }\n            findContainingIntervals(x, m + 1, b, result);\n        }\n    }\n\n    java.util.Collection<Interval> findContainingIntervals(double x) {\n        java.util.Collection<Interval> result  = new java.util.ArrayList<Interval>();\n        findContainingIntervals(x, 0, intervals.length, result);\n        return result;\n    }\n\n    Interval[] intervals;\n    double[] maxEnd;\n\n    public static void main(String[] args) {\n        java.util.Random r = new java.util.Random();\n        Interval[] intervals = new Interval[10000];\n        for (int j = 0; j < intervals.length; j++) {\n            Interval i = new Interval();\n            do {\n                i.begin = r.nextDouble();\n                i.end = r.nextDouble();\n            } while (i.begin >= i.end);\n            intervals[j] = i;\n        }\n        IntervalTree it = new IntervalTree(intervals);\n        double x = r.nextDouble();\n        java.util.Collection<Interval> result = it.findContainingIntervals(x);\n        int count = 0;\n        for (Interval i : intervals) {\n            if (i.begin <= x && x <= i.end) {\n                count++;\n            }\n        }\n        System.out.println(result.size());\n        System.out.println(count);\n    }\n}\n

\n