我有一些在x轴上以其开始和结束x坐标形式呈现的加粗线段。一些线段可能重叠。如何找到所有线段的联合长度。
例如，一条线段是5,0到8,0，另一条是9,0到12,0。两者不重叠，因此长度之和为3+3=6。
一条线段是5,0到8,0，另一条是7,0到12,0。但它们在范围7,0到8,0重叠。因此，长度的联合为7。
但x坐标可能是浮点数。
寻找多条线段的并集长度
4
- Shashwat Kumar
4
1将所有坐标排序，同时跟踪其是开放端还是关闭端。然后通过线性循环进行遍历，并使用计数器来计算我们当前所在的线段数量 - 并在适当时添加到前一个端点的距离差。 - nhahtdh
我期望不超过N log n。 - Shashwat Kumar
浮点数有多精确？是2、3还是4位小数？您可以尝试实现此答案中提供的算法。 - HamZa
@ShashwatKumar：假设排序算法是O（n log n），则它的时间复杂度为O（n log n）。 - nhahtdh
4个回答
1
将线段表示为2个EndPoint对象。每个EndPoint对象的形式为<coordinate，isStartEndPoint>。将所有线段的EndPoint对象放在一个列表endPointList中。
算法：
- 按坐标升序排列
endPointList，首先将起始端点放在尾端点前面（不管是哪个线段，因为这没有关系-它们都在同一个坐标上）。 根据以下伪代码循环遍历排序后的列表：
prevCoordinate = -Inf numSegment = 0 unionLength = 0 for (endPoint in endPointList): if (numSegment > 0): unionLength += endPoint.coordinate - prevCoordinate prevCoordinate = endPoint.coordinate if (endPoint.isStartCoordinate): numSegment = numSegment + 1 else: numSegment = numSegment - 1
由于基于比较的排序算法具有Omega（n log n）的下限，而循环在最佳情况下显然是O（n），所以复杂度主要受到排序部分的影响。因此，如果选择O（n log n）的基于比较的排序算法，则该算法的复杂度可以说是O（n log n）。
- nhahtdh
0
使用范围树。范围树的时间复杂度是n log(n)，就像排序的起始/结束点一样，但它还有一个额外的优势，即重叠的范围将减少元素的数量（但可能会增加插入的成本）。代码片段（未经测试）
struct segment {
struct segment *ll, *rr;
float lo, hi;
};
struct segment * newsegment(float lo, float hi) {
struct segment * ret;
ret = malloc (sizeof *ret);
ret->lo = lo; ret->hi = hi;
ret->ll= ret->rr = NULL;
return ret;
}
struct segment * insert_range(struct segment *root, float lo, float hi)
{
if (!root) return newsegment(lo, hi);
/* non-overlapping(or touching) ranges can be put into the {l,r} subtrees} */
if (hi < root->lo) {
root->ll = insert_range(root->ll, lo, hi);
return root;
}
if (lo > root->hi) {
root->rr = insert_range(root->rr, lo, hi);
return root;
}
/* when we get here, we must have overlap; we can extend the current node
** we also need to check if the broader range overlaps the child nodes
*/
if (lo < root->lo ) {
root->lo = lo;
while (root->ll && root->ll->hi >= root->lo) {
struct segment *tmp;
tmp = root->ll;
root->lo = tmp->lo;
root->ll = tmp->ll;
tmp->ll = NULL;
// freetree(tmp);
}
}
if (hi > root->hi ) {
root->hi = hi;
while (root->rr && root->rr->lo <= root->hi) {
struct segment *tmp;
tmp = root->rr;
root->hi = tmp->hi;
root->rr = tmp->rr;
tmp->rr = NULL;
// freetree(tmp);
}
}
return root;
}
float total_width(struct segment *ptr)
{
float ret;
if (!ptr) return 0.0;
ret = ptr->hi - ptr->lo;
ret += total_width(ptr->ll);
ret += total_width(ptr->rr);
return ret;
}
- wildplasser
2
这是区间树吗？抱歉，但这是我第一次听到“范围树”的名称。 - nhahtdh
可能是这样。我只是选择了出现的第一个名字。 - wildplasser
0
这是我刚刚用Haskell编写的解决方案，下面是如何在解释器命令提示符中实现它的示例。段落必须以元组列表[(a,a)]的形式呈现。我希望您可以从代码中了解算法的意义。
import Data.List
unionSegments segments =
let (x:xs) = sort segments
one_segment = snd x - fst x
in if xs /= []
then if snd x > fst (head xs)
then one_segment - (snd x - fst (head xs)) + unionSegments xs
else one_segment + unionSegments xs
else one_segment
*Main> :load "unionSegments.hs"
[1 of 1] 正在编译 Main ( unionSegments.hs, 解释型 )
好的，模块已加载: Main.
*Main> unionSegments [(5,8), (7,12)]
7
- גלעד ברקן
0
Java实现
import java.util.*;
公共类 HelloWorld {
static void unionLength(int a[][],int sets)
{
TreeMap<Integer,Boolean> t=new TreeMap<>();
for(int i=0;i<sets;i++)
{
t.put(a[i][0],false);
t.put(a[i][1],true);
}
int count=0;
int res=0;
int one=1;
Set set = t.entrySet();
Iterator it = set.iterator();
int prev=0;
while(it.hasNext()) {
if(one==1){
Map.Entry me = (Map.Entry)it.next();
one=0;
prev=(int)me.getKey();
if((boolean)me.getValue()==false)
count++;
else
count--;
}
Map.Entry me = (Map.Entry)it.next();
if(count>0)
res=res+((int)me.getKey()-prev);
if((boolean)me.getValue()==false)
count++;
else
count--;
prev=(int)me.getKey();
}
System.out.println(res);
}
public static void main(String []args){
int a[][]={{0, 4}, {3, 6},{8,10}};
int b[][]={{5, 10}, {8, 12}};
unionLength(a,3);
unionLength(b,2);
}
}
- lucky
1
请随时提出建议，帮助我改进这段代码。 - lucky
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接