[Java] 距离交点算法优于O(n)?


Answers

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

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日志):

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

搜索:

  1. 使用二分查找找到> = TestRange.End的第一个数据透视表
  2. 遍历树直到数据透视表> 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,我不在数据库中。

这个问题似乎是非常相似的存储二维点快速检索矩形内的那些,但我不知道它是如何映射的。

那么,你将存储一组范围的数据结构,使得范围上的搜索成本小于O(n)? (使用可用于Java的库的额外功劳)

编辑:

我想获得所有相交范围的子集,这意味着搜索范围可以与多个范围相交。

Java中需要小于O(n)的方法是:

public class RangeSet {
    ....
    public Set<Range> intersects(Range range);
    ....
}

其中Range只是一个包含一对int开始和结束的类。

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




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

正如有些人指出的那样,如果所有的范围碰巧与目标范围相交(例如,如果目标范围是{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和其他一些系统一样重叠? 你仍然想找到与你的目标重叠的所有地区/“元素”,但是他们不是那么容易组织的。

另一方面,你应该能够做得很好,因为许多应用程序中的标记范围通常很小 - 书中的单词,句子和段落比章节中的要多得多。 所以即使在目标之前可能有大量的范围,并且在它之后会有一个巨大的数字,平均而言,这个交点将会非常小。

我认为这就是最初的提问者,恐怕我没有看到解决这个问题的答案。 如果这不是原来的问题,那么我想把它作为一个新的问题。




正如四叉树适用于一组二维点,一个简单的二叉树应该适用于这种情况。 用你的范围构建一棵树。

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

  - 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)

进一步的细节:二叉树的结构就像四叉树的一维版本。 每个节点将有三个整数(对不起,我上面说了两个,但现在我意识到你需要三个),最低代表在这个节点下面的最低范围的最低值,最高代表在此之下的最高范围的最高值节点和枢轴。 左边的孩子将从这个节点的最低点到其枢轴点。 正确的孩子将从这个节点的枢轴跨越到这个节点的最高点。 如果只有一个从“最低”到“最高”的范围,那么你将不会有一个关键点,这将是一片叶子。 理想情况下,你会选择每个节点的支点来保持树的平衡。




这取决于你确切的问题,在链接的问题,不同的范围,没有共同的部分,搜索范围可以跨越多个范围。 如果你的问题是一样的,那么它很容易:取一个范围数组,按最小值排序(因为它们不重叠,这也是按照它们的上面的值排序的顺序)。

现在就为你的目标下限值(如果不是精确的话)做一个bin搜索,为目标上限值(如果不是确切的话就更大一些)做一个bin搜索。 由此产生的索引是覆盖的范围。 你必须检查指标本身的范围是否被排除,但这只是2个检查。 整体复杂度O(log n)。