算法来计算相交光盘数量 [英] Algorithm to calculate number of intersecting discs

问题描述

下面是一个在线测试的一部分，但它现在这么IM希望它确定后在这里被删除。我挣扎的答案，所以我想请问聪明的人的计算器。任何语言是好的！

The following was part of an online test but its been removed now so Im hoping its ok to post here. I am struggling with the answer so I thought I ask the smart people on StackOverflow. Any language is fine!

由于N个整数的数组，我们得出ñ盘在2D平面上，这样，第i个盘在中心（0，i）和半径A [1]。我们说k个盘和第j个圆盘相交，如果

Given an array A of N integers we draw N discs in a 2D plane, such that i-th disc has center in (0,i) and a radius A[i]. We say that k-th disc and j-th disc intersect, if

和第k个和第j个盘具有至少一个公共点。

and k-th and j-th discs have at least one common point.

写一个函数

int number_of_disc_intersections(int[] A);

其中给定的阵列甲描述Ñ光盘，如上所述，返回对相交的光盘的数目。例如，给定N = 6以及

which given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and

A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0

有11对相交光盘的：

there are 11 pairs of intersecting discs:

0th and 1st
0th and 2nd
0th and 4th
1st and 2nd
1st and 3rd
1st and 4th
1st and 5th
2nd and 3rd
2nd and 4th
3rd and 4th
4th and 5th

这样的函数应该返回11。 该函数应该返回-1，如果相交对的数目超过千万。该函数可以假定N不超过10,000,000。

so the function should return 11. The function should return -1 if the number of intersecting pairs exceeds 10,000,000. The function may assume that N does not exceed 10,000,000.

任何人能帮助我这个好吗？

Anyone able to help me out with this please?

推荐答案

所以，你要查找的区间交叉点的数目 [的iA [I]，1 + A [1]] 。

So you want to find the number of intersections of the intervals [i-A[i], i+A[i]].

维护包含的iA [I] （也有一些额外的空间，其值为 I + A排序后的数组（称之为X） [我] 在那里）。

Maintain a sorted array (call it X) containing the i-A[i] (also have some extra space which has the value i+A[i] in there).

现在走阵列X，开始在最左边的时间间隔（即最小的iA [I] ）。

Now walk the array X, starting at the leftmost interval (i.e smallest i-A[i]).

对于目前的区间，做一个二进制搜索，看看那里的区间的右端点（即 1 + A [1] ）会（被称为排名）。现在你知道它相交的所有元素的左侧。

For the current interval, do a binary search to see where the right end point of the interval (i.e. i+A[i]) will go (called the rank). Now you know that it intersects all the elements to the left.

递增与职级计数器和减去当前位置（假设索引），因为我们不希望重复计算的时间间隔和自相交。

Increment a counter with the rank and subtract current position (assuming one indexed) as we don't want to double count intervals and self intersections.

O（nlogn）的时间， O（N）的空间。

这篇关于算法来计算相交光盘数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！