求intersect的圆，求O(nlogn)的方法 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求intersect的圆，求O(nlogn)的方法

求intersect的圆，求O(nlogn)的方法# JobHunting - 待字闺中

l*r2014-08-29 07:08

1 楼

一道很简单的面试题：
给一个数组arr[]，数组第i个元素表示圆心坐标为(0,i)，半径为arr[i]的圆。求出该
数组里有多少个圆心不同但intersect的圆？
题目很简单，但是小弟只能答出简单的解法，用两个循环一个个找，想不出time
complexity是O(nlogn)的解法。
求各位高手给个思路。

p*n2014-08-29 07:08

2 楼

对于每个圆 i，和它的半径r[i]=arr[i], 我们可以考虑这个圆和x-轴的左右两个交点
［start_i, end_i］, 其中start_i = i - array[i] and end_i = i+ array[i];
我们先将所有的圆，按照start_i 排序，然后一个一个的加入，这个题是要求出，每
次加入一个圆i，有多少个圆k (0 <=k < i) 和第i个圆相交。实质上就是说每加入一个
［start_i, end_i］有多少个 [start_k, end_k] ( 0 <= k < i) 和［start_i,
end_i］相交，然后对（i = 0...n) 求和就好。
我们按照start index排序，如果 k < i 也就是 start_k < start_i, 那么两个圆［
start_k, end_k］和［start_i, end_i］相交的判定条件是 start_i . 那么这个题就是要用binary search （或者用BST来实现）找到每个圆［start_i,
end_i］加入的时侯 (1) end_i 在｛end1. end2 ….. end_i-1｝的位置 a，和 (2)
start_i在｛end1. end2 ….. end_i-1｝的位置 b。这两个位置的间距 a - b 就是
有多少个圆和第i个圆重合。
我们需要将每个已经加入的圆的end_k (0<= k <= i-1)都放到一个self-balanced 的
BST中。然后每个node都要记录有多少个圆的end index比这个node的值小。 (好久之前
版上讨论过，实现有点太复杂了，就不说了)。这样查找 a 和b 的位置的时间复杂度都
是log(n).
总复杂度所以为O(nlogn)

d*j2014-08-29 07:08

3 楼

基本sweep line的做法。好好看看clsr上里面找任意两个线段是否相交的算法，稍微
修改就ok了。没记错的话这是其中一个习题。

【在 l**********r 的大作中提到】

: 一道很简单的面试题：
: 给一个数组arr[]，数组第i个元素表示圆心坐标为(0,i)，半径为arr[i]的圆。求出该
: 数组里有多少个圆心不同但intersect的圆？
: 题目很简单，但是小弟只能答出简单的解法，用两个循环一个个找，想不出time
: complexity是O(nlogn)的解法。
: 求各位高手给个思路。

l*r2014-08-29 07:08

4 楼

弱问：clsr是什么？ ⊙﹏⊙b

【在 d***j 的大作中提到】

: 基本sweep line的做法。好好看看clsr上里面找任意两个线段是否相交的算法，稍微
: 修改就ok了。没记错的话这是其中一个习题。

l*r2014-08-29 07:08

5 楼

汗，刚刚知道introduction to algorithm这本书简称clrs…… 惭愧惭愧

【在 d***j 的大作中提到】

: 基本sweep line的做法。好好看看clsr上里面找任意两个线段是否相交的算法，稍微
: 修改就ok了。没记错的话这是其中一个习题。