r*********n 发帖数: 32 | 1 就是给一堆interval,是在二维平面上的线段。把重合的线段都合并起来。
class Interval {
Point start;
Point end;
}
class Point {
int x; int y;
}
开始是想直接按照斜率和 start.x 排序就好了,结果发现不对,只能维持一个merge好
的序列,for循环往后,对于每个interval,找起点是不是在之前某个interval 组成的
线段上,这样时间复杂度是O(N^2),
各位大神有什么想法? |
m**********s 发帖数: 518 | 2 目测用x^2+y^2排序,然后退化为按斜率的interval合并问题
【在 r*********n 的大作中提到】 : 就是给一堆interval,是在二维平面上的线段。把重合的线段都合并起来。 : class Interval { : Point start; : Point end; : } : class Point { : int x; int y; : } : 开始是想直接按照斜率和 start.x 排序就好了,结果发现不对,只能维持一个merge好 : 的序列,for循环往后,对于每个interval,找起点是不是在之前某个interval 组成的
|
l**********0 发帖数: 150 | 3 Groupby斜率进入map,每map内部的线段列表sortby x,y
【在 r*********n 的大作中提到】 : 就是给一堆interval,是在二维平面上的线段。把重合的线段都合并起来。 : class Interval { : Point start; : Point end; : } : class Point { : int x; int y; : } : 开始是想直接按照斜率和 start.x 排序就好了,结果发现不对,只能维持一个merge好 : 的序列,for循环往后,对于每个interval,找起点是不是在之前某个interval 组成的
|
F****n 发帖数: 3271 | 4 以斜率+截距为key建立hashtable
value为interval tree
【在 r*********n 的大作中提到】 : 就是给一堆interval,是在二维平面上的线段。把重合的线段都合并起来。 : class Interval { : Point start; : Point end; : } : class Point { : int x; int y; : } : 开始是想直接按照斜率和 start.x 排序就好了,结果发现不对,只能维持一个merge好 : 的序列,for循环往后,对于每个interval,找起点是不是在之前某个interval 组成的
|
s*****p 发帖数: 30 | 5 每个interval 所在的直线都和 x轴有一个交点 (x, 0)(和x轴平行的也要另外考虑)
能不能对于每个interval 计算出这个x的值和, 然后按x和斜率分组。
各个组内 在 interval[(x1, y1), (x2, y2)] 退化成[x1, x2], 然后按照x 排序 再
merge? |
s******u 发帖数: 9 | 6 不知道这样行不行:可以自由平移的话就每个线段可以看作矢量(xend-xstart, yend-
ystart),然后搜索相等或相反的矢量就行了
【在 r*********n 的大作中提到】 : 就是给一堆interval,是在二维平面上的线段。把重合的线段都合并起来。 : class Interval { : Point start; : Point end; : } : class Point { : int x; int y; : } : 开始是想直接按照斜率和 start.x 排序就好了,结果发现不对,只能维持一个merge好 : 的序列,for循环往后,对于每个interval,找起点是不是在之前某个interval 组成的
|
S*********r 发帖数: 42 | 7 1. First group by slope, log(N)
2. Within the same slope group, check colinearity by checking whether the
line of two starts has the same slope
3. Then we can merge the colinear lines |