一种优于O(n)的距离求交算法?

标准方法是使用 interval tree .

在计算机科学中,区间树是用来保存区间的树数据结构。具体而言,它允许有效地找到与任何给定间隔或点重叠的所有间隔。它通常用于窗口查询,例如,在矩形视口中查找计算机化地图上的所有道路,或在三维场景中查找所有可见元素。类似的数据结构是段树。

听起来这个解决方案或多或少是可行的 an Interval Tree . 可以找到更完整的间隔树实现 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日志n):

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

搜索:

2. 遍历树直到轴>测试范围。开始

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

范围:

• 0 - 2
• 1 - 2
• 2 - 3
• 1 - 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

非重叠范围:

准备O(n日志n):

1. 制作范围的数组/向量。
2. 按范围的末尾对向量进行排序(按范围的开头排序以断开关系)

搜索:

1. 使用二进制搜索查找结束值为>=测试范围。开始

2. 迭代器,从二进制搜索开始,直到找到开始>测试范围。结束:

   2a。如果当前范围在TestRange范围内,则将其添加到结果中。

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

现在只需搜索一个binsearch,搜索目标较低的值(如果不精确,则搜索较小的值),搜索一个binsearch,搜索目标较高的值(如果不精确,则搜索较大的值)。结果索引是覆盖的范围。您必须检查索引本身的范围是否在-或排除范围内,但这只是两个检查。总体复杂度O(logn)。

重叠范围:

准备O(n日志n):

1. 制作范围的数组/向量。

3. 生成第二个整数向量。这表示可以停止搜索的点。

   int stop[size];
   stop[size-1] = Ranges[size - 1].start;
   for (int i = size - 2; i >= 0; i--)
   {
       stop[i] = min(Ranges[i].start, stop[i+1]);
   }
   

1. 使用二进制搜索查找结束值为>=测试范围。开始

2. 迭代器从二进制搜索开始,直到停止[i]>测试范围。结束:

   2a。如果当前范围在TestRange范围内,则将其添加到结果中。

对于重叠(或包含)给定目标范围的范围,上述大多数解决方案似乎不起作用。

正如一些人指出的,如果(最坏情况) 全部的

做

考虑一个文本文档的简单情况,该文本文档为其“类型”标记了不同区域,也许您希望找到包含或交叉给定给定连续文本范围的所有标记单元(例如,段落)。在HTML、XML或类似语言中,这些只能是包含至少一些目标范围字符的文本节点的祖先。在每个节点上都有父指针的典型表示中,这是O(m)——比O(n)好得多,特别是因为m(对于较短或同步的目标范围)仅仅是树嵌套深度,这往往比ln(n)还要低,因为实际上大型XML文档变得更密集而不是更深。

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

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

听起来您需要一个实现SortedSet接口的类。TreeSet是核心API附带的实现。

然后,可以使用内存中的集合实现与数据库算法等效的算法。

至于这是否真的比O(n)快,我不能说。

正如四叉树适用于一组二维点一样,简单的二叉树也适用于这种情况。用你的范围建立一棵树。

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

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

进一步详情: 二叉树的结构类似于四叉树的一维版本。每个节点将有三个整数(抱歉,我上面说了两个,但现在我意识到您需要三个),最低值表示此节点下方最低范围的最低值,最高值表示此节点下方最高范围的最高值,以及轴。左边的子节点将从该节点的最低节点延伸到其轴。右边的子节点将从该节点的轴延伸到该节点的最高点。如果只有一个从“最低”到“最高”的范围,你就没有轴心,这将是一片叶子。理想情况下,您应该为每个节点选择枢轴,以保持树的平衡。

当我遇到这个问题时,我使用范围的排序数组和二进制搜索来查找交点。这是(我相信)O(logn)性能,在处理重叠范围时有一点开销。

我认为,你的问题的答案是可以从下面的代码中推导出来的,但不能插入。我展示了整个代码,以避免因不同的上下文而产生混淆-我需要在代码点范围列表中插入一系列Unicode代码点。

--编辑--

调整下面的代码以确定多个范围的交点需要从插入点开始进行简单的前向搜索,直到找到不再相交的范围。

--结束编辑--

final int                               lower;                                  // lower end of range
final int                               upper;                                  // upper end of range

public int compareTo(Object obj) {
    if(obj==null) { return -1; }

    Range                           oth=(Range)obj;

    if(lower<oth.lower) { return -1; }
    if(lower>oth.lower) { return  1; }
    if(upper<oth.upper) { return -1; }
    if(upper>oth.upper) { return  1; }
    return 0;
    }

public Builder addRange(int fir, int las) {
    if(fir!=-1) { fir&=0x001FFFFF; }
    if(las!=-1) { las&=0x001FFFFF; }

    if(codepoints==null || codepoints.length==0) {
        codepoints=new Range[]{new Range(fir,las)};
        }
    else {
        int                         idx=Range.findChar(codepoints,fir);
        int                         ins=(idx<0 ? -(idx+1) : idx);

        if(idx<0) {
            if     (ins>0                 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); }  // new range adjoins the following range (can't overlap or idx would be >=0)
            else if(ins<codepoints.length && las>=(codepoints[ins  ].lower-1)) { idx=ins;     }  // new range overlaps or adjoins the following range
            }

        if(idx<0) {
            codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
            }
        else {
            boolean                 rmv=false;

            for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
                if(las<codepoints[xa].upper) { las=codepoints[xa].upper; }
                codepoints[xa]=null;
                rmv=true;
                }
            if(codepoints[idx].lower>fir || codepoints[idx].upper<las) {
                codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
                }
            if(rmv) { codepoints=Range.removeNulls(codepoints); }
            }
        }
    return this;
    }

static int findChar(Range[] arr, int val) {
    if(arr.length==1) {
        if     (val< arr[0].lower) { return -1; }                             // value too low
        else if(val<=arr[0].upper) { return  0; }                             // value found
        else                       { return -2; }                             // value too high
        }
    else {
        int                             lowidx=0;                               // low index
        int                             hghidx=(arr.length-1);                  // high index
        int                             mididx;                                 // middle index
        Range                           midval;                                 // middle value

        while(lowidx<=hghidx) {
            mididx=((lowidx+hghidx)>>>1);
            midval=arr[mididx];
            if     (val< midval.lower) { hghidx=(mididx-1); }                   // value too low
            else if(val<=midval.upper) { return mididx;     }                   // value found
            else                       { lowidx=(mididx+1); }                   // value too high
            }
        return -(lowidx+1);                                                     // value not found.
        }
    }