[java] 范围交叉算法优于O(n)?


Answers

编辑:听起来这个解决方案或多或少是一个间隔树 。 可以在here找到更完整的间隔树实现。

class TreeNode
{
public:
    long pivot;
    List<Range> leaves;  //Any ranges that intersect the pivot
    TreeNode left;        //Tree nodes that fall to the left of the pivot
    TreeNode right;       //Tree nodes that fall to the right of the pivot
};

准备O(n log n):

  1. 创建范围列表
  2. 选择枢轴点(可能使用结束日期的排序列表。)??
  3. 建立你的树。

搜索:

  1. 使用二进制搜索来查找> = TestRange.End的第一个数据透视表
  2. 遍历树,直到pivot> TestRange.Start

    2A。 将叶子添加到结果中。

例:

范围:

  • 0 - 2
  • 1 - 2
  • 2 - 3
  • 1 - 4
  • 2 - 4
  • 0 - 5
  • 4 - 5
  • 2 - 6
  • 3 - 7

树:

                             4
               --------------+------------------
               3             |                 7
               |            1-4                |
               |            2-4                |
               |            0-5                |
               |            4-5                |
      ---------+------                 --------+--------
      2        |    null              6        |       null
 -----+----   2-3                 ----+----   3-7
null  |  null                   null  |  null    
     0-2                             2-6
     1-2
Question

范围交叉是一个简单但非平凡的问题。

已经回答了两次:

第一个解决方案是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的类。

这不是一个不可能的问题,我已经有了解决方案,我只是想看看是否有更标准/更简单的方法




就像四叉树适用于一组2d点一样,一个简单的二叉树应该适用于这种情况。 用你的范围构建一棵树。

进一步解释:树中的每个节点包含两个整数,范围的开始和结束,以及两个子节点(如果它不是叶节点)。 要查找输入范围跨越的范围,请从树的顶部开始

  - if the node range intersects the input range:
     - if it's a leaf node, then add the range to your result list
     - if it's not a leaf node, then traverse down to the child nodes and repeat this process.

它应该是O(logN)

更多细节:二叉树的结构类似于四叉树的一维版本。 每个节点都有三个整数(抱歉我上面说过两个,但现在我意识到你需要三个),最低值表示低于此节点的最低值的最低值,最高值表示低于此值的最高值的最高值节点和枢轴。 左边的孩子将从这个节点的最低点到其枢轴。 正确的孩子将从此节点的枢轴跨越到此节点的最高点。 如果只有一个范围从“最低”到“最高”,你将没有一个支点,这将是一片叶子。 理想情况下,您需要为每个节点选择枢轴以保持树的平衡。




如果范围重叠,并且想要检索重叠(或包含)给定目标范围的所有范围,则上述大多数解决方案似乎不起作用。

正如一些人所指出的,如果(最坏情况) 所有范围恰好与目标范围相交(例如,如果目标范围是{0..MAXINT}或类似),那么当然需要O(n)返回n范围。

但是不是有趣且典型/平均的情况,其中n个总范围中只有很小一部分与目标范围相交? 调用与“m”相交的数字 - 在这种情况下,你可以想象能够做到与O(m)一样好。 如果n = 10 ^ 9且m = 10,则这是一个成败的区别。

考虑一个文本文档的简单情况,该文档具有为其“类型”标记的各种区域 - 可能您希望找到包含或交叉给定连续文本范围的所有标记单元(例如,段落)。 在HTML,XML或类似的中,它们只能是包含目标范围的至少一些字符的文本节点的祖先。 在每个节点中具有父指针的典型表示中,O(m) - 方式优于O(n),特别是因为m(对于短或同步目标范围)仅仅是树嵌套深度,其往往甚至低于ln(n)因为实际上大的XML文档变得越来越粗糙。

有趣的情况更难:如果您的“元素”不像XML那样形成树,但可以像MECS,CLIX,LMNL和其他一些系统那样重叠? 您仍然希望找到与目标重叠的所有区域/“元素”,但它们不是那么容易组织的。

另一方面,你应该能够做得很好,因为许多应用程序中的标记范围通常很小 - 书中的单词,句子和段落比章节要多得多。 因此,即使可能有大量的范围在目标之前开始,而大量的范围在其之后结束,但交叉点的平均值非常小。

我认为这就是原始提问者所得到的,我担心我没有看到解决该问题的答案。 如果它不是原始问题的内容,那么我想把它作为一个新问题。




这取决于您的确切问题,在链接的问题中,不同的范围,没有共同的部分,以及搜索的范围可能跨越多个范围。 如果您的问题是相同的,那么它非常简单:取一个范围数组,按它们的最低值排序(因为它们不重叠,这也是按其上限值排序的顺序)。

现在只需对目标较低的值进行binsearch(如果不精确,则为较小值),对目标较高值进行一次binsearch(如果不精确,则为较大值)。 结果索引是覆盖的范围。 您必须检查索引本身的范围是在 - 或排除,但这只是2次检查。 总体复杂度O(log n)。




Links