l**********r
发帖数: 7 | 1 一道很简单的面试题：
给一个数组arr[]，数组第i个元素表示圆心坐标为(0,i)，半径为arr[i]的圆。求出该
数组里有多少个圆心不同但intersect的圆？
题目很简单，但是小弟只能答出简单的解法，用两个循环一个个找，想不出time
complexity是O(nlogn)的解法。
求各位高手给个思路。 |
p********n
发帖数: 165 | 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***j
发帖数: 593 | 3 基本sweep line的做法。 好好看看clsr上里面找任意两个线段是否相交的算法， 稍微
修改就ok了。没记错的话这是其中一个习题。
【在 l**********r 的大作中提到】
: 一道很简单的面试题：
: 给一个数组arr[]，数组第i个元素表示圆心坐标为(0,i)，半径为arr[i]的圆。求出该
: 数组里有多少个圆心不同但intersect的圆？
: 题目很简单，但是小弟只能答出简单的解法，用两个循环一个个找，想不出time
: complexity是O(nlogn)的解法。
: 求各位高手给个思路。
|
l**********r
发帖数: 7 | 4 弱问：clsr是什么？ ⊙﹏⊙b
【在 d***j 的大作中提到】
: 基本sweep line的做法。 好好看看clsr上里面找任意两个线段是否相交的算法， 稍微
: 修改就ok了。没记错的话这是其中一个习题。
|
l**********r
发帖数: 7 | 5 汗，刚刚知道introduction to algorithm这本书简称clrs…… 惭愧惭愧
【在 d***j 的大作中提到】
: 基本sweep line的做法。 好好看看clsr上里面找任意两个线段是否相交的算法， 稍微
: 修改就ok了。没记错的话这是其中一个习题。
|
h****g
发帖数: 105 | |
y*******8
发帖数: 112 | 7 排序需要nlogn
【在 h****g 的大作中提到】
: sweep line 的话就可以O(n)了吧？
|
